杭电OJ 1722 与 2504 对比:GCD的简单理解
C语言中GCD函数用于求两个数的最大公约数,杭电OJ中的两个简单水题涉及GCD函数的简单运用。
1722
代码如下(其中注有较为详细的说明)
#include<stdio.h>
int GCD(int p,int q)
{
if(p%q == 0)
return q;
//若p能被q整除,则它们的最大公因数为q
int a;
a = p % q;
GCD(q,a);
}//辗转相除法
int main()
{
int p, q;//据题意输入两个数
int b;//代表两数的最大公因数
int ans;
while(scanf("%d%d", &p, &q) != EOF)
{
b = GCD(p,q);//利用GCD函数计算出最大公因数
ans = p + q - b;
//答案等于两数之和减去它们的最大公因数
printf("%d\n", ans);
}
return 0;
}
2504题目如下
相比于1722题来说,2504题的难度稍有增加,难度应该在于理解题意吧,再将其转换为简单的数学问题。
以上一段都是废话,代码如下
#include<stdio.h>
int GDC(int a, int b)
{
if(a%b == 0)
return b;
else
return GDC(b,a%b);
}
int main()
{
int a, b, c;
int n;
scanf("%d", &n);
while(n--)
{
int a, b, c;
scanf("%d%d", &a, &b);
//考虑到三个数均不为零,且b,c不相等,则c要从2b开始加起
for(c = b * 2; c <= a; )
{
if(GDC(a,c) == b)
break;
else
c = c + b;
}
printf("%d\n", c);
}
return 0;
}
PS:不难理解,在1722题中的代码,GCD函数求最大公约数的方法就是辗转相除法。