（light oj 1024） Eid （最小公倍数）-白红宇

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

阅读量：5213 次

发布时间：2019-06-14

本文共 2513 字，大约阅读时间需要 8 分钟。

题目链接：

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.InputInput starts with an integer T (≤ 225), denoting the number of test cases.Each case of input will contain an integer n (2 ≤ n ≤ 1000) 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 1 and 10000.OutputFor 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 Input232 20 1045 6 30 60Output for Sample InputCase 1: 20Case 2: 60

题目大意：给出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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include 
            #include 
             
              #include 
              
               #include
               
                using namespace std;#define N 100006#define INF 0x3f3f3f3f#define LL long long#define mod 1000000007int prim[N];int arr[N],ans[N];int k =0;void Init()///先打个素数表{ memset(arr,0,sizeof(arr)); for(int i=2;i<=105;i++) { if(!arr[i]) { prim[k++] = i; for(int j=i;j<=105;j+=i) arr[j] = 1; } }}void mul(int n)///大数相乘{ for(int i=0;i<1000;i++) ans [i] = ans[i]*n; for(int i=0;i<1000;i++) { ans[i+1] +=ans[i]/10000; ans[i] = ans[i]%10000; }}void prin()///大数输出{ int i = 1000; while(i>=0 && !ans[i]) i--; printf("%d",ans[i--]); while(i>=0) printf("%04d",ans[i--]); printf("\n");}int main(){ int T; int con=1; Init(); scanf("%d",&T); while(T--) { int n,num; scanf("%d",&n); memset(arr,0,sizeof(arr)); for(int i=0;i
                
                 1) arr[num] = max(arr[num],1);///这个数为素数 } memset(ans,0,sizeof(ans)); ans[0] = 1; for(int i=0;i<10001;i++) { if(!arr[i]) continue; int sum = 1; for(int j=0;j