题目:
代码:
#includeint common(int a,int b)//计算最大公约数{ int c=a%b,t=0; if(b>a) { t=b; b=a; a=t; } while(a%b!=0) { c=a%b; a=b; b=c; } return b;}int q[105];int main(){ int n,i,j,t=0; while(scanf("%d",&n)) { for(i=1;i<=n;i++) { scanf("%d",&q[i]); } t=q[1]; //printf("%d\n",common(4,6)); for(j=2;j<=n;j++) { t=q[j]*t/common(q[j],t);//重复计算其公倍数 } printf("%d\n",t); } return 0;}
TLE
最大的问题是每次计算都要调用common函数,每次调用都要执行for循环,计算比较多的数导致TLE是正常的事情。
参考代码:by acmcyc
#includeusing namespace std;int main(){ int n,i; int a[100]; while(cin>>n) { int max; cin>>a[0]; max=a[0]; for(i=1;i >a[i]; if(a[i]>max) max=a[i]; } int k=0,j; for(j=max;;j++)//2 5 7 j=7; { for(i=0;i
看到这串代码,不得不佩服作者的思考角度和方法:先找出输入所有数中的最大数max,然后不断+1进行判断(最小公倍数大于等于max),如果找到一个数对输入的所有数都能整除,那么这个数就是他们的最小公倍数。