（light oj 1024） Eid （最小公倍数）

题目链接： http://lightoj.com/volume_showproblem.php?problem=1024

In a strange planet there are n races. They are completely different as well as their food habits. Each race has a food-eating period. That means the ith race eats after every xi de-sec (de-sec is the unit they use for counting time and it is used for both singular and plural). And at that particular de-sec they pass the whole day eating.

The planet declared the de-sec as 'Eid' in which all the races eat together.

Now given the eating period for every race you have to find the number of de-sec between two consecutive Eids.

Input

Input starts with an integer T (≤ ), denoting the number of test cases.

Each case of input will contain an integer n ( ≤ n ≤ ) in a single line. The next line will contain n integers separated by spaces. The ith integer of this line will denote the eating period for the ith race. These integers will be between  and .

Output

For each case of input you should print a line containing the case number and the number of de-sec between two consecutive Eids. Check the sample input and output for more details. The result can be big. So, use big integer calculations.

Sample Input

Output for Sample Input

Case :

Case :
 

题目大意：给出n个数  求n个数的最小公倍数；

思路：求最小公倍数可以用最大公约数来求，但是由于n的大小与每个数的大小，所以最后说求得最小公倍数可能是个大数，所以需要用到大数相乘；

利用每个数的因子求最小公倍数。例如：

5 的因子 5；

6的因子 2 3；

30的因子 2 3 5；

60的因子 2 2 3 5；

保存出现的每个因子最大个数  2个2 1个3 1个5 相乘就得到最小公倍数 60；

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<math.h>

#include<queue>

#include<stack>

#include <map>

#include <string>

#include <vector>

#include<iostream>

using namespace std;

#define N 100006

#define INF 0x3f3f3f3f

#define LL long long

#define mod 1000000007

int prim[N];

int arr[N],ans[N];

int  k =;

void Init()///先打个素数表

{

    memset(arr,,sizeof(arr));

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

    {

        if(!arr[i])

        {

            prim[k++] = i;

            for(int j=i;j<=;j+=i)

                arr[j] = ;

        }

    }

}

void mul(int n)///大数相乘

{

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

        ans [i] = ans[i]*n;

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

    {

        ans[i+] +=ans[i]/;

        ans[i] = ans[i]%;

    }

}

void prin()///大数输出

{

    int i = ;

    while(i>= && !ans[i]) i--;

    printf("%d",ans[i--]);

    while(i>=)

        printf("%04d",ans[i--]);

    printf("\n");

}

int main()

{

    int T;

    int con=;

    Init();

    scanf("%d",&T);

    while(T--)

    {

        int n,num;

        scanf("%d",&n);

        memset(arr,,sizeof(arr));

        for(int i=;i<n;i++)

        {

            scanf("%d",&num);

            for(int j=;j<k&&prim[j]*prim[j]<=num;j++)

            {

                int s = ;

                while(num%prim[j]==)///统计每个数每个因子的个数

                {

                    s++;

                    num = num/prim[j];

                }

                arr[prim[j]] = max(s,arr[prim[j]]);///保存当前因子最多的个数

            }

            if(num>)

                arr[num] = max(arr[num],);///这个数为素数

        }

        memset(ans,,sizeof(ans));

        ans[] = ;

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

        {

            if(!arr[i]) continue;

            int sum = ;

            for(int j=;j<arr[i];j++)

                sum = sum*i;

            mul(sum);///每个因子相乘

        }

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

        prin();

    }

    return ;

}