【lightoj-1024】Eid （高精度）

【题意】

给定n个数，求这n个数的最小公倍数。

【题解】

最小公倍数当然不能按常规方法来求，因为最大的数将近是10000^1000级别的。然鹅最小公倍数怎么搞呢？

这里发现了一个规律：

4

5 6 30 60

5 : 5 //说明最小公倍数的因子中一定有一个5

6 : 2*3 //说明最小公倍数的因子中一定有一个2和一个3;

30 : 2*3*5 //说明最小公倍数的因子中一定有一个2和一个3和一个5;

60 : 2^2*3*5 //说明最小公倍数的因子中一定有2个2和一个3和一个5;

所以我们可以忽略那些个数比较少的， 找到说明结果中一定含有 2个2 1个3 1个5;

最后要用到高精度乘法。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int a[], b[];

void Mul(int b[], LL n)

{

    int i;

    for(i = ; i <= b[]; i++) b[i] *= n;

    for(i = ; i <= b[]; i++) b[i+] += b[i] / , b[i] %= ;

    while(b[i]) b[i+] += b[i] / , b[i] %= , i++, b[]++;

}

LL q_pow(int x, int y)

{

    LL ans = ;

    while(y)

    {

        if(y&) ans *= x;

        x *= x;

        y >>= ;

    }

    return ans;

}

int main()

{

    int t, n, i, cas = , m;

    cin>>t;

    while(t--)

    {

        scanf("%d", &n);

        memset(a, , sizeof(a));

        int max1 = ;

        while(n--)

        {

            scanf("%d", &m);

            max1 = max(max1, m);

            for(i = ; i <= m; i++)

            {

                int tep = ;

                while(m % i == )

                    tep++, m /= i;

                a[i] = max(a[i], tep);

            }

        }

        memset(b, , sizeof b);

        b[] = , b[] = ;

        for(i = ; i <= max1; i++)

        {

            if(a[i] != )

                Mul(b, q_pow(i, a[i]));

        }

        printf("Case %d: ", ++cas);

        for(i = b[]; i >= ; i--)

            printf("%d", b[i]);

        cout<<endl;

    }

    return ;

}