首页 > ACM题库 > HDU-杭电 > HDU 4139-Big Division-数学相关-[解题报告]HOJ
2015
04-16

HDU 4139-Big Division-数学相关-[解题报告]HOJ

Big Division

问题描述 :

A theoretical physicist friend is doing research about the "Answer to the Ultimate Question of Life, the Universe, and Everything", he thinks that it is not 42 as suggested by “The Hitchhiker’s Guide to the Galaxy” science fiction comedy series; instead he thinks it is the result of dividing the products of two sequences of positive integers A and B!
The task of calculating the product of A and B followed by division turned out to be not as easy as it looks, specially with the sequences being long and the products getting too large very quickly! Even using a modern computer, a straight forward implementation for the calculations may take very long time to complete! And this is where we seek your help as a brilliant computer scientist!

输入:

The first line of input contains an integer (1 <= T <= 200), the number of test cases.
T test cases follow, the first line of each test case contains two integers (1 <= N, M<= 110,000), the lengths of sequences A and B respectively. Two lines follow, the first line contains N space separated integers (0 < A0, A1 … An <= 1,000,000), and the second line contains M space separated integers (0 < B0, B1 … Bm <= 1,000,000).

输出:

The first line of input contains an integer (1 <= T <= 200), the number of test cases.
T test cases follow, the first line of each test case contains two integers (1 <= N, M<= 110,000), the lengths of sequences A and B respectively. Two lines follow, the first line contains N space separated integers (0 < A0, A1 … An <= 1,000,000), and the second line contains M space separated integers (0 < B0, B1 … Bm <= 1,000,000).

样例输入:

2
3 1
2 4 5
12
2 4
1 15
5 1 7 2

样例输出:

Case #1: 10 / 3
Case #2: 3 / 14

简单的数学题,化简分数,做法是分别记录分子和分母的素因子个数,分子的加1,分母的加-1,这样最后个数为0的就代表已经约去,有个小优化,找一个数的素因子的时候用上,快了300ms….Orz,具体看代码

#define N 1000005
int max(int a,int b){return a>b?a:b;}
LL cnt[N];
void gao(int n,int p){
    int i;
    int a=1;
    for(i=2;i*i<=n;i+=a,a=2){//加一个小优化,可以省下300ms,因为素因子中除了2,3相差1之外其它都至少相差2
        if(n%i==0){
            while(n%i==0){
                cnt[i] += p;
                n/=i;
            }
        }
    }
    if(n>1)cnt[n] += p;
}
int main(){
    int t;
    scanf("%d",&t);
    int ca=1;
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        int i,j;
        int a,b;
        memset(cnt,0,sizeof(cnt));
        int maxm = 0;
        for(i=0;i<n;i++){
            scanf("%d",&a);
            maxm = max(a,maxm);
            gao(a,1);
        }
        for(j=0;j<m;j++){
            scanf("%d",&b);
            maxm = max(b,maxm);
            gao(b,-1);
        }
        int x = 1,y = 1;
        for(i=2;i<=maxm;i++){
            if(cnt[i] > 0){
                while(cnt[i]--){
                    x *= i;
                }
            } else if(cnt[i]<0){
                while(cnt[i]++){
                    y *= i;
                }
            }
        }
        printf("Case #%d: %d / %d\n",ca++,x,y);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/leolin_/article/details/7301586