首页 > 代码库 > n个数的最大公约、最小公倍数

n个数的最大公约、最小公倍数

 

 

 1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 #define N 1010 5  6 //两个数的最大公约数和最小公倍数 7 __int64 Gcd(__int64 a, __int64 b) 8 { 9     if(b==0)10         return a;11     return Gcd(b, a%b);12 }13 14 __int64 Lcm(__int64 a, __int64 b)15 {16     return a/Gcd(a, b)*b;17 }18 19 //n个数的最大公约数和最小公倍数20 __int64 nGcd(__int64 *a, int n)21 {22     if(n==1)23         return *a;24     return Gcd(a[n-1], nGcd(a, n-1));25 }26 __int64 nLcm(__int64 *a, int n)27 {28     if(n==1)29         return *a;30     return Lcm(a[n-1], nLcm(a, n-1));31 }32 int main()33 {34     int t;35     __int64 a[N], n;36     scanf("%d", &t);37     while(t--)38     {39         scanf("%I64d", &n);40         for(int i=0; i<n; i++)41             scanf("%I64d", a+i);42         __int64 tp = nLcm(a, n);43         printf("%I64d\n",tp);44     }45 }

 

n个数的最大公约、最小公倍数