如果有一个自然数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的最大公约数的函数及测试主程序如下。
#include<stdio.h>
int 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 <stdio.h>
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 <stdio.h>
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）源程序。
#include<stdio.h>
int 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 <stdio.h>
#include <string.h>
#define MAXN 1001
int 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）源程序。
#include<stdio.h>
long 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 <stdio.h>
#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 3101 Astronomy （http://poj.org/problem?id=3101） ，可以Accepted。
【练习1】POJ1284 Primitive Roots （http://poj.org/problem?id=1284）。
#include <stdio.h>
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 <stdio.h>
#define MAXN 65536
int 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 <stdio.h>
#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 <stdio.h>
#include <string.h>
#define MAXN 1000005
int 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）。
#include<stdio.h>
long 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;
}
参考程序
标签：return,gcd,int,long,最大公约数,互质
From： https://www.cnblogs.com/cs-whut/p/16987103.html