最小公倍数大数问题

 1  #include<stdio.h>
 2  #include<string.h>
 3  #define N 50
 4  int len,a[N]={1};
 5  char tab[100][45]={0,1};
 6  inline int gcd(int a,int b)
 7  {
 8      return b==0?a:gcd(b,a%b);
 9  }
10  int mod(int t) //求余
11  {
12      int i,k;
13      for(k=0,i=len-1;i>=0;--i){
14          k=(k*10+a[i])%t;
15      }
16      return k;
17  }
18  void fun(int m,int n)  //乘以m再除以n
19  {
20      int i,j,k,c;
21      int s[N];
22      for(c=i=0;i<len+2;++i){
23          k=a[i]*m+c;
24          a[i]=k%10;
25          c=k/10;
26      }
27      for(i=len+1;i>=0&&!a[i];--i);
28      len=i+1;
29      for(k=j=0,i=len-1;i>=0;--i){
30          k=k*10+a[i];
31          s[j++]=k/n;
32          k%=n;
33      }
34      len=j;
35      memset(a,0,sizeof(a));
36      for(i=0;i<len;++i)
37          a[i]=s[len-i-1];
38      for(i=len;!a[i];--i);
39      len=i+1;
40  }
41  int main()
42  {
43      int i,j,k,t,n;
44      for(len=1,i=2;i<=100;++i){//打表
45          t=mod(i);
46          if(t){
47              k=gcd(i,t);
48              fun(i,k);
49          }
50          for(tab[i-1][0]=j=len-1;j>=0;--j)
51              tab[i-1][j+1]=a[j];
52      }
53      while(~scanf("%d",&n)){
54          for(j=tab[n-1][0]+1;j>0;--j)
55              printf("%d",tab[n-1][j]);
56          printf("
");
57      }
58      return 0;
59  }

View Code

考虑到1-100的最小公倍数肯定超出__int64.所以需要转化成字符串问题来解

仔细观察会发现，【1-n】的最小公倍数，是【1-n-1】的最小公倍数乘以n的所有素因子中没有被【1-n-1】包含的素因子。

例如：【1-7】的最小公倍数是2*3*2*5*7，8=2*2*2,(8中2出现3次，【1-7】的素因子中只出现2次)那么【1-8】就是2*3*2*5*7*2

最小公倍数 大数问题

最小公倍数大数问题