2011蓝桥杯 最小公倍数 NOYJ517

2
3
4

2
6
12

ACM_杨延玺

思路：首先看到题应该注意，它是求1~n个数的最小公倍数，所以这道题是对多个数求最小公倍数，即原来的最小公倍数=两数乘积/最大公约数，就不能在这里用了。

这里通过找规律后才可总结出思路（惊叹别人的思想）

1=1     2=2    3=3

4=2*2    5=5     6=2*3

7=7       8=2*2*2     9=3*3     10=2*5 通过这里可以看出每个数都可以写成一个或多个素数的乘积。通过观察可以发现前n位数的最小公倍数

的公式。

例如前4位数的最小公倍数ans[4]=1*2*3*2=12.  怎么来的呢？

是前四项的因数相乘得到。其中factor[1](因数1)=1  factor[2]=2  factor[3]=3   factor[4]=2，为什么第四位的因数为2,？这是因为前面已经有

一个2，相当于抵消掉一个2（可以这么理解）  即factor[5]=5  factor[6]=1（抵消factor[2]与factor[3]）   factor[9]=3（抵消factor[3]）

所以前n为的最小公倍数即前n项因子之积。这里需要用到大数乘法概念，因为前100位最小公倍数太大 ，long long存不下。

以下为代码：

#include<stdio.h>
#include<string.h> 
int factor[101];
char ans[105][100];
void getfactor()//求出因数 
{for(int i=1;i<=100;i++){factor[i]=i;for(int j=2;j<i;j++)if(factor[i]%factor[j]==0)factor[i]=factor[i]/factor[j];}	
}
void bigmul()//相乘 
{int sum,k=0,j,b;ans[1][0]='1';ans[1][1]='\0';for(int i=2;i<=100;i++){b=factor[i];for(j=0,k=0;j<strlen(ans[i-1]);j++){sum=(ans[i-1][j]-'0')*b+k;k=sum/10;ans[i][j]=sum%10+'0';}while(k){ans[i][j]=k%10+'0';k/=10;j++;}}
}
void print(int n)//输出前N为最小公倍数 
{for(int i=strlen(ans[n])-1;i>=0;i--)printf("%c",ans[n][i]);printf("\n");
}
int main()
{getfactor();bigmul();int n;while(scanf("%d",&n)!=EOF){print(n);}/*for(int i=1;i<=100;i++){printf("%s",ans[i]);if(i%3==0) printf("\n");}*/return 0;
}