如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数。几个自然数公有的约数,叫做这几个自然数的公约数。公约数中最大的一个公约数,称为这几个自然数的最大公约数(Greatest Common Divisor,简写为GCD)。例如,自然数12和30的公约数有1、2、3、6,其中6就是12和30的最大公约数。

求最大公约数有多种方法,常见的有辗转相除法、短除法、更相减损法、质因数分解法等。

1.辗转相除法

辗转相除法的基本做法是用较大的数除以较小的数,若余数为0,则其中较小的数(即除数)就是最大公约数;若余数不为0,则用前面较小的除数和得出的余数构成新的一对数,继续做上面的除法,直到出现能够整除的两个数(余数为0)。

下面以求48和27的最大公约数为例,求解过程如下:

48 ÷ 27 = 1余 21

27 ÷ 21 = 1余6

21 ÷ 6 =3余3

6 ÷ 3=2

所以3就是48和27的最大公约数。

辗转相除法使用到的原理也很简单,假设用f(x, y)表示x,y的最大公约数,取k = x/y,b = x%y,则x = ky + b,如果一个数能够同时整除x和y,则必能同时整除b和y;而能够同时整除b和y的数也必能同时整除x和y,即x和y的公约数与b和y的公约数是相同的,其最大公约数也是相同的,则有f(x, y)= f(y, x%y)(y > 0),如此便可把原问题转化为求两个更小数的最大公约数,直到其中一个数为0,剩下的另外一个数就是两者最大的公约数。

采用辗转相除法编写的求两个整数m和n的最大公约数的函数及测试主程序如下。

#includeint gcd(int m,int n){    int r=m%n;    while (r!=0)    {        m = n;        n = r;        r =    m%n;    }    return n;}int main(){    int m,n,t;    while (scanf("%d %d",&m,&n)!=EOF)    {        t = gcd(m,n);        printf("%d\n",t);    }    return 0;}

这个函数也可以写成递归的形式,如下。

int gcd(int m,int n){    if (m%n==0) return n;    return gcd(n,m%n);}

2.短除法。

短除法是不断地找两个数的最小公约数,直到找不到为止,然后把所有的最小公约数乘起来,就是最大公约数。

下面以求48和36的最大公约数为例,操作如下:

从除1外的最小的约数2开始试探起

48 ÷ 2 = 24 36 ÷ 2 =18 ,2是约数

24 ÷ 2 = 12 18 ÷ 2 =9 , 2还是约数

12 ÷ 3 = 4 9 ÷ 3 =3 , 3是约数

4和3不存在公约数,结束。

所以,2×2×3=12就是48和36的最大公约数。

采用短除法编写的求两个整数m和n的最大公约数的函数如下。

int gcd(int m,int n){    int i,r = 1;    for (i=2;i<=m && i<=n;i++)    {        while (m%i==0&&n%i==0)        {            r = r*i;            m = m/i;            n = n/i;        }    }    return r;}

3.更相减损法。

更相减损术出自于中国古代的《九章算术》,也是一种求最大公约数的算法,其基本方法是:

  ① 先判断两个数的大小,如果两数相等,则这个数本身就是就是它的最大公约数。

   ② 如果不相等,则用大数减去小数,然后用这个较小数与它们相减的结果相比较,如果相等,则这个差就是它们的最大公约数;如果不相等,则继续执行②操作。

例如,求24与15的最大公约数的逐步减损过程如下:

(24,15) -> (9,15) -> (9,6) -> (3,6) -> (3,3)

所以,3就是24和15的最大公约数。

采用更相减损法编写的求两个整数m和n的最大公约数的函数如下。

int gcd(int m,int n){    int t;    while (m!=n)    {        if (m<n) {t=m;  m=n;  n=t; }        m=m-n;    }    return n;}

4.Stein算法。

Stein算法由J. Stein 1961年提出,这个方法在计算两个数的最大公约数时,只有整数的移位和加减法,对于程序来说,运算方便效率高。

Stein算法的基本原理是:

1)若a和b都是偶数,则记录下公约数2,然后都除以2(右移1位);

2)若其中一个数是偶数,则偶数除以2,因为此时2不可能是这两个数的公约数了;

3)若两个都是奇数,则a = |a-b|,b = min(a,b),因为若d是a和b的公约数,那么d也是|a-b|和min(a,b)的公约数。

设gcb(a,b)表示求整数a、b的最大公约数,则这个算法可描述为

当a和b均为偶数时,gcb(a,b) = 2gcb(a/2, b/2) = 2 * gcb(a>>1, b>>1);

当a为偶数,b为奇数时,gcb(a,b) = gcb(a/2, b) = gcb(a>>1, b)

当a为奇数,b为偶数时,gcb(a,b) = gcb(a, b/2) = gcb(a, b>>1)

当a和b均为奇数,利用更相减损术运算一次,gcb(a,b) = gcb(b, a-b),此时a-b的结果必然是偶数,又可以继续进行移位运算。

采用Stein算法编写的求两个整数m和n的最大公约数的函数如下。

int gcd(int m,int n){    int p=1,t;    while (m%n!=0)    {        if (m<n) { t=m;  m=n;  n=t; }        if (m%2==0)        {            if (n%2==0) { p=p*2; m=m>>1; n=n>>1; }            else  { m=m>>1; }        }        else        {            if (n%2==0) { n=n>>1; }            else       { m=m-n;  m=m>>1; }        }    }    return p*n;}

这一算法可以写成递归的形式,如下。

int gcd(int m,int n){    if (m < n)    {        int tmp = m;        m = n;        n = tmp;    }    if (m%n==0)  return n;    if (m % 2 == 0 && n % 2 == 0)        return 2*gcd(m >> 1, n >> 1);    else if (m%2 == 0 && n%2 != 0)        return gcd(m >> 1, n);    else if (m%2 != 0 && n % 2 == 0)        return gcd(m, n >> 1);    else if (m % 2 != 0 && n % 2 != 0)        return gcd(n, (m - n) >> 1);}

【例1】最大最小公倍数。

问题描述

已知一个正整数N,问从1~N中任选出三个数,他们的最小公倍数最大可以为多少。

输入

输入一个正整数N(1 <= N <= 106)。

输出

输出一个整数,表示你找到的最小公倍数。

输入样例

9

输出样例

504

(1)编程思路。

设有整数x和y,若x和y的最大公约数为k,则它们的最小公倍数为x*y/k。显然,若k=1,则x和y的最小公倍数才尽可能大。因此,要在1~N中选尽可能大的3个互质(最大公约数为1)的数,它们的最小公倍数才最大。

显然,x与x-1是互质的,x-1与x-2也是互质的。当然 x 与 x-2就不一定互质了。若 x是偶数,它们就存在约数2。若x是奇数,x与x-2也是互质的。

因此,在1~N中要选3个数的话,若N是奇数,就直接选 N、N-1和N-2这3个数,它们彼此互质,最小公倍数就是N*(N-1)*(N-2),为最大。

若N是偶数,则先选N、N-1和N-3这3个数,若这3个数互质,则满足要求;若不互质,则选N-1、N-2和N-3这3个数即可。

(2)源程序。

#include int gcd(int a,int b){    if (a%b==0) return b;    else return gcd(b,a%b);}int main(){    int n,n1,n2,n3;    scanf("%d",&n);    if (n%2==1)    {        n1=n;  n2=n-1;    n3=n-2;    }    else    {        n1=n;        n2=n-1;        n3=n-3;        while (gcd(n1,n3)!=1 || gcd(n2,n3)!=1) n3--;        if (n3!=n-3)        {            n1=n-1; n2=n-2;    n3=n-3;        }    }    long long ans;    ans=1ll*n1*n2*n3;    printf("%lld\n",ans);    return 0;}

【例2】最大公约数和最小公倍数问题。

问题描述

输入二个正整数x0,y0(2<=x0<=100000,2<=y0<=100000),求出满足下列条件的P,Q的个数

条件: 1.P,Q是正整数

   2.要求P,Q以x0为最大公约数,以y0为最小公倍数.

试求:满足条件的所有可能的两个正整数的个数。

输入

两个数x0,y0

输出

一个数表示答案

输入样例

3 60

输出样例

4

(1)编程思路。

显然P和Q的最小值为x0,最大值为y0,直接对P进行穷举即可。并且穷举时,P的值的变化是 x0、2*x0、3*x0、…直到y0。

(2)源程序。

#include int gcd(int m, int n){    int r;    while(m%n!=0)    {        r=m%n;        m = n;        n = r;    }    return n;}int main(){    int x,y,i,cnt=0;    scanf("%d%d",&x,&y);    for(i=x;i<=y;i+=x)  // 因为所求的两个数都是x的整数倍,所以每次加x        if ((x*y)%i==0&& gcd(x*y/i,i)==x) // ∵i*j=x*y ∴j=x*y/i ∴只要枚举i既可            cnt++;    printf("%d\n",cnt);    return 0;}

将上面的源程序提交给洛谷题库P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题 (https://www.luogu.com.cn/problem/P1029),可以Accepted。

【例3】第k个与M互质的数。

问题描述

如果两个整数的最大公因数(GCD)为1,则两个正整数被称为彼此互质的。例如,1、3、5、7、9……都与2006是互质的。

对于给定的整数m,当把与m互质的数按升序排列后,找到第K个数,它与m是互质的。

输入

输入包含多个测试用例。对于每个测试用例,它包含两个整数m(1<=m<=1000000)、K(1<=K<=100000000)。

输出

在单行中输出第K个元素。

输入样例

2006 1

2006 2

2006 3

输出样例

1

3

5

(1)编程思路。

因为 gcd(a+b*k,b)=gcd(b,a%b), gcd(a,b)=gcd(b,a%b),

所以 gcd(a+b*k,b)=gcd(a, b), k为常数。

这表明了:对于与b互质的数,它们对b取模的余数会周期性出现。

故只需要计算出在b的范围内, 与b互质的数有哪些。然后看第k个与b互质的数是在第几个周期的第几个就可以了。

(2)源程序。

#includeint s[1000005];int gcd(int a,int b){    int r;    while (a%b!=0)    {        r=a%b;        a=b;        b=r;    }    return b;}int main(){    int m,k,i,num;    while (scanf("%d%d",&m,&k)!=EOF)    {        num=0;        for(i=1;i<=m;i++)           {            if(gcd(m,i)==1)            {                s[num++]=i;            }        }        if (k%num==0)        {            printf("%d\n",(k/num-1)*m + s[num-1]);        }        else        {            printf("%d\n",k/num*m + s[k%num-1]);        }    }    return 0;}

将上面的源程序提交给北大POJ题库 POJ 2773 Happy 2006 (http://poj.org/problem?id=2773),可以Accepted。

【例4】可见的点。

问题描述

对于除原点(0,0)外的第一象限的任意一个格点(x,y)(x和y是大于或等于0的整数),如果从(0,0)到(x,y)的连线没有穿过任何其它的格点,则称格点(x,y)是从原点可见的。

例如,点(4,2)不可见,因为来自原点的线穿过了(2,1),如下图所示。也就是说前面的点(2,1)可以挡住后面的点(4,2)。

编写一个程序,在给定大小N的值后,计算可见点(x,y)的数量,其中0≤ x、y≤N。

输入

第一行输入包含单个整数C(1≤C≤1000),表示测试用例的数量。

每个测试用例由包含单个整数N(1≤ N≤ 1000)的单行输入组成。

输出

对于每个测试用例,都有一行输出,包括:从1开始的测试用例编号、N的大小以及该大小下可见点的数量,数据间用空格分隔。

输入样例

4

2

4

5

231

输出样例

1 2 5

2 4 13

3 5 21

4 231 32549

(1)编程思路。

本题实际上就是要求在这个N*N的网格上从原点到各格点的直线有多少种不同的斜率。

边上的两点先不管,然后将整个正方形分成上三角和下三角两部分,由于对称性,两边可以看到的点的数目肯定一样多。以下三角为例进行说明。

1×1只有一个斜率为0的。

2×2 斜率有0,1/2(0已经算过了,以后不再算了),其实就多了一个斜率为1/2的。

3×3 斜率有1/3,2/3两个,比以前多了2个。

4×4 斜率有1/4,2/4(1/2已经有过了),3/4,所以也是2个。

5×5 斜率有1/5,2/5,3/5,4/5,之前都没有,所以多了4个

6×6 斜率有1/6,2/6(1/3已经有了),3/6(1/2已经有了),4/6(2/3已经有了),5/6,所以只多2个。

更一般地 n×n,可以从0,0连接到(n,0)到(n,n)上,斜率将会是1/n,2/n,……,(n-1)/n。

由此发现,对于所有能看到的点,它们有着一个共同的特征,

那就是gcd(x,y)=1,若不为1,则它前面肯定有一个点挡住了这个点。

由此问题就转换为:对于一个数n,求小于n的与n互质的数的个数,这就是欧拉函数。

欧拉函数的定义: E(k)=([1,n-1]中与n互质的整数个数)。

因为任意正整数k都可以唯一表示成如下形式:

k=p1^a1*p2^a2*……*pi^ai;(即分解质因数形式)

可以推出: E(k)=(p1-1)(p2-1)……(pi-1)*(p1^(a1-1))(p2^(a2-1))……(pi^(ai-1))

=k*(p1-1)(p2-1)……(pi-1)/(p1*p2*……pi);

=k*(1-1/p1)*(1-1/p2)….(1-1/pk)

利用欧拉函数如下性质,可以快速求出欧拉函数的值(a为N的质因子)。

若 (N%a==0 && (N/a)%a==0) 则有 E(N)=E(N/a)*a;

若 (N%a==0 && (N/a)%a!=0) 则有 E(N)=E(N/a)*(a-1);

计算好下三角后,最终结果=下三角的个数×2 再加1(斜率为1的点)。

(2)源程序。

#include #include <string.h>#define  MAXN  1001int main(){    int c,n,i,j,sum;    int prime[MAXN], pNum, phi[MAXN];    bool  vis[MAXN];    memset(vis,true,sizeof(vis));    //  下面程序段既求MAXN以内的质数又求欧拉数。    pNum=0;    phi[1] = 1;    for (i = 2; i < MAXN; i++)    {        if (vis[i])       // i是质数        {             prime[pNum++] = i;             phi[i] = i-1;        }        for (j = 0; j < pNum && prime[j]*i <MAXN; j++ )        {            vis[prime[j]*i] = false;            if (i % prime[j] == 0)            {                phi[i*prime[j]] = phi[i] * prime[j];                break;            }            else                 phi[i*prime[j]] = phi[i] *(prime[j] - 1);        }    }    scanf("%d", &c);    for (i =1; i <=c; i++)    {        scanf("%d", &n);        sum = 0;        for (j = 1; j <= n ; j++)        {            sum += phi[j];        }        printf("%d %d %d\n", i, n, 2 * sum + 1);    }    return 0;}

将上面的源程序提交给北大POJ题库 POJ 3090 Visible Lattice Points (http://poj.org/problem?id=3090),可以Accepted。

【例5】最大公约数之和。

问题描述

给定一个整数N(1<N<2^31),计算∑gcd(i,N) 1<=i<=N。

输入

输入包含多个测试用例。

每行一个整数N。

输出

对于每个N个输出1-N中所有的数与N的最大公约数的和。

输入样例

2

6

输出样例

3

15

(1)编程思路。

设x与n的最大公约数是a,也就是gcd(x,n)=a,那么我们就可以知道gcd(x/a,n/a)=1,也就是x/a与n/a互质。

这说明在1-n中与 n 的最大公约数为a的数都与n/a互质,所以我们可以用欧拉函数求出1-n/a中,与n/a互质的数有多少个,其中,a是n的约数,所以遍历所有n的约数。

本题要求的是1~n中各数与n的最大公约数的和sum,所以可以枚举N的所有约数,当a是n的约数时,和值sum就加上a*euler(n/a)。

其中, euler(x) 是欧拉函数,其返回值是 1 到 x 中有多少个数字与 x 互质。

(2)源程序。

#includelong long euler(long long x){    long long i,ret=x;    for (i=2;i*i<=x;i++)    {        if (x%i==0) ret=ret/i*(i-1);        while (x%i==0) x/=i;    }    if (x>1) ret=ret/x*(x-1);    return ret;}int main(){    long long n;    while (scanf("%lld",&n)!=EOF)    {        long long i,ans=0;        for (i=1;i*i<=n;i++)        {           if (n%i==0)           {               ans+=euler(n/i)*i;               if (i*i!=n)               {                  ans+=euler(i)*(n/i);               }           }        }        printf("%lld\n",ans);    }    return 0;}

将上面的源程序提交给北大POJ题库 POJ 2480 Longge’s problem (http://poj.org/problem?id=2480),可以Accepted。

【例6】行星共线。

问题描述

X星的行星系统中有n颗行星,它们以位于同一平面的圆形轨道围绕X星运行。每个行星的角速度是恒定的。所有行星的轨道方向都是相同的。

编写程序求连续两次所有行星和恒星X位于同一直线上的时间间隔长度。

输入

输入文件的第一行包含n-行星数(2≤ n≤ 1000)。

第二行包含n个整数ti-行星的轨道周期(1≤ti≤10000),并非所有的ti都是相同的。

输出

将答案输出为不可约分数,用空格分隔分子和分母。

输入样例

3

6 2 3

输出样例

3 1

(1)编程思路。

任意两颗行星共线,其运行距离差为半个周长的整数倍即可。

已知每个行星的角速度为vi = 2*π/ti,选择一个行星T0作为坐标系,则其他行星的相对速度为vi’ = (2*π/t0-2*π/ti) = (t0 – ti)*2π/(t0*ti),则角度绕过半个圆周的时间为Ti’ = π/vi’ = (t0*ti)/((t0 – ti)*2)。

所求的答案就是求所有Ti‘的分子的最小公倍数LCM和所有Ti’分母的最大公约数GCD。

由于题目给定2≤n≤1000,1≤ti≤10000,因此最小公倍数会超出长整数表数范围,需要采用高精度计算。在求最小公倍数时,采用将最小公倍数分解质因数的方法,即将LCM分解为Π(pi^bi)的形式,最后根据这个分解式计算出所有Ti的最小公倍数即可。

另外,在求Ti’=(t0*ti)/((t0 – ti)*2)的时候先对分子和分母进行约分,这样就能够保证最后分子分母互质。

(2)源程序。

#include #include <string.h>int prime[5000],pcnt=0;void init()    // 生成10000以内的质数表{    int i,j;    int vis[10005]={0};    for (i=2;i<10000;i++)    {       if (!vis[i])       {           prime[pcnt++]=i;           for (j=2*i;j<10000;j+=i)               vis[j]=1;       }    }}int gcd(int a,int b){    if (b==0) return a;    return gcd(b,a%b);}int lcm(int a,int b){    return a*b/gcd(a,b);}int abs(int x){     return x>0?x:-x;}int main(){     init();     int n;     while (scanf("%d",&n)!=EOF)     {         int fm=0;         int fz[1001];       // 用于保存分子(各数的最大公约数),是一个大整数,每个元素保存4位数字         int p[5001];        // 用于保存各数最小公倍数的质因子的指数         memset(p,0,sizeof(p));         memset(fz,0,sizeof(fz));         int i,j,t[1001];         for (i=0;i<n;i++)             scanf("%d",&t[i]);         for (i=1;i<n;i++)         {             if (t[i]==t[0]) continue;             int tmp1=lcm(t[i],t[0]);             int tmp2=2*abs(tmp1/t[i]-tmp1/t[0]);             int temp=gcd(tmp1,tmp2);             tmp1/=temp;                   // 分子与分母约分,保证两两互质               tmp2/=temp;             fm=gcd(fm,tmp2);              // 求分母的最大公约数             for (j=0;j<pcnt;j++)          // 将分子的最小公倍数分解质因数             {                 int cnt=0;                 while (tmp1%prime[j]==0)                 {                     cnt++;  tmp1/=prime[j];                 }                 if (p[j]<cnt) p[j]=cnt;   // 保存质因数prime[j]较大的指数                 if (tmp1==1)break;             }         }         fz[0]=1;                          // 按各质因子及指数求得分子         int len=1;                        // 分子大整数的位数(按万进制)         for (i=0;i<pcnt;i++)         {             for (j=0;j<p[i];j++)             {                 int k,cf=0;                 for (k=0;k<len;k++)                 {                     fz[k]=fz[k]*prime[i]+cf;                     cf=fz[k]/10000;                     fz[k]%=10000;                 }                 if (cf!=0) fz[len++]=cf;             }         }         printf("%d",fz[len-1]);         for (i=len-2;i>=0;i--)             printf("%04d",fz[i]);         printf(" %d\n",fm);     }     return 0;}

将上面的源程序提交给北大POJ题库POJ 3101Astronomy (http://poj.org/problem?id=3101) ,可以Accepted。

【练习1】POJ1284 Primitive Roots (http://poj.org/problem?id=1284)。

#include int getPhiValue(int n) // 求n的欧拉函数值phi(n){    int i,sum,t;    sum = n;    t=n;    for (i=2;i*i<=t;i++)      if (t % i == 0) // 找到一个质因数i      {         sum -= sum/i;         while (t % i == 0) // 将质因数i全去掉           t /= i;      }    if (t!=1) sum -= sum/t;    return sum;}int main(){    int p;    while (scanf("%d", &p) !=EOF)    {        printf("%d\n",getPhiValue(p-1));    }    return 0;}

参考程序1

#include #define  MAXN  65536int phi[MAXN];int prime[MAXN], pNum;int vis[MAXN]={0};void getPhiTable(int n) // 求2~n的欧拉函数值phi[i] (1<i<=n){    int i,j;    pNum=0;    phi[1] = 1;    for (i = 2; i < MAXN; i++)    {        if (vis[i]==0)            //  i是素数        {            prime[pNum++] = i;            phi[i] = i-1;        }        for (j = 0; j < pNum && prime[j]*i <MAXN; j++ )        {           vis[prime[j]*i] = 1;           if (i % prime[j] == 0)           {               phi[i*prime[j]] = phi[i] * prime[j];               break;           }           else               phi[i*prime[j]] = phi[i] *(prime[j] - 1);        }    }}int main(){    int p;    getPhiTable(MAXN);    while (scanf("%d", &p) !=EOF)    {        printf("%d\n",phi[p-1]);    }    return 0;}

参考程序2

【练习2】POJ 1580 String Matching (http://poj.org/problem?id=1580)。

// 采用穷举法搜索两串匹配的首字母,不断更新最大匹配值即可,// 最后的答案需要对最大匹配值和两串总长进行约分 #include #include <string.h> int gcd(int x,int y){    int r;      while (x%y!=0)    {        r=x%y;        x=y;        y=r;      }    return y;}int min(int x,int y){    return x<y?x:y;}int main(){    int i,j,k,len1,len2,a,b,res,max;    char c1[1000],c2[1000];    while(1)    {        scanf("%s",c1);        if(strcmp(c1,"-1")==0)             break;        scanf("%s",c2);        len1=strlen(c1);        len2=strlen(c2);        max=0;              for(i=0;i<len1;i++)       // 穷举两字符串首字母             for(j=0;j<len2;j++)            {                res=0;                    for(k=0;k<min(len1-i,len2-j);k++)                    if(c1[k+i]==c2[k+j])                        res++;                if (max<res) max=res;            }         if(max==0||2*max-len1-len2==0)            printf("appx(%s,%s) = %d\n",c1,c2,2*max/(len1+len2));        else        {            a=2*max;            b=len1+len2;            i=gcd(a,b);            a/=i;            b/=i;            printf("appx(%s,%s) = %d/%d\n",c1,c2,a,b);        }    }    return 0;}

参考程序

【练习3】POJ 2478 Farey Sequence (http://poj.org/problem?id=2478)。

#include #include <string.h>#define  MAXN  1000005int prime[MAXN], pNum, phi[MAXN];long long num[MAXN]={0};int vis[MAXN];int main(){    int n,i,j;    memset(vis,1,sizeof(vis));    pNum=0;    phi[1] = 1;    for (i = 2; i < MAXN; i++)    {        if (vis[i])       // i是素数        {            prime[pNum++] = i;            phi[i] = i-1;        }        for (j = 0; j < pNum && prime[j]*i <MAXN; j++ )        {            vis[prime[j]*i] = 0;            if (i % prime[j] == 0)            {                phi[i*prime[j]] = phi[i] * prime[j];                break;            }            else                phi[i*prime[j]] = phi[i] *(prime[j] - 1);        }    }    for (i=2;i<MAXN;i++)    {        num[i]=num[i-1]+phi[i];    }    while (scanf("%d", &n) && n!=0)    {        printf("%lld\n",num[n]);    }    return 0;}

参考程序

【练习4】POJ 3002 Jackpot (http://poj.org/problem?id=3002)。

#includelong long gcd(long long a,long long b){    if (a%b==0) return b;    return gcd(b,a%b);}long long lcm(long long a,long long b){    return a/gcd(a,b)*b;}int main(){    int t;    scanf("%d",&t);    while(t--)    {        int i,n;        scanf("%d",&n);        long long a,b;        scanf("%lld",&a);        for (i=1;i<n;i++)        {            scanf("%lld",&b);            a=lcm(a,b);        }        if (a<=1000000000)            printf("%lld\n",a);        else            printf("More than a billion.\n");    }    return 0;}

参考程序