小记:WA了一次。原因就是因为题目说lie within in the range of a 32-bit integer... 所以我在gcd和lcm的时候都是用int。然后导致了wa。改过来就AC了。
思路:从左到右一次求最小公倍数,对后来加的新数,让其与之前的所有的数的最小公倍数一起求两者的最小公倍数,直到算到最后一个数。答案及出来了。
原理证明:
lcm(a,b) = a*b/gcd(a,b)
gcd(a,b,c) = gcd(gcd(a,b),c)// 这点很简单
...
推广:
gcd(a,b...n) = gcd(gcd(...gcd(a,b),....n)
lcm(a,b...n) = lcm(lcm(...lcm(a,b),...n)
求gcd代码:
long long gcd(long long a,long long b){ return b?gcd(b,a%b):a; }
利用欧几里得求gcd:
long long gcd(long long a,long long b){ long long r = a%b; while(r){ a = b; b = r; r = a%b; } return b; }
求LCM代码:
long long lcm(long long a,long long b){ return a/gcd(a,b)*b; }
AC码:
#include <iostream> #include <cstdio> using namespace std; long long gcd(long long a,long long b){ return b?gcd(b,a%b):a; } long long lcm(long long a,long long b){ return a*b/gcd(a,b); } int main(){ //freopen("f:\\out.txt","w",stdout); long long T, n, m,t; cin>>T; while(T--){ cin>>n; cin>>t; while(--n){ cin>>m; t = lcm(m,t); } cout<<t<<endl; } return 0; }
最小公倍数的一篇文章,里面有利用位运算求gcd。仅供参考:
http://zh.wikipedia.org/wiki/%E6%9C%80%E5%B0%8F%E5%85%AC%E5%80%8D%E6%95%B8