Question

杭电2504题为什么WA？跪求大牛解释？？？

又见GCD
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4020 Accepted Submission(s): 1632

Problem Description
有三个正整数a,b,c(0<a,b,c<10^6)，其中c不等于b。若a和c的最大公约数为b，现已知a和b，求满足条件的最小的c。

Input
第一行输入一个n，表示有n组测试数据，接下来的n行，每行输入两个正整数a,b。

Output
输出对应的c，每组测试数据占一行。

Sample Input
2
6 2
12 4

Sample Output
4
8

Source
《ACM程序设计》短学期考试_软件工程及其他专业

Recommend
lcy
代码是
#include<stdio.h>
main()
{
int ri,repeat;
__int32 i,a,b,c;
scanf("%d",&repeat);
for(ri=1;ri<=repeat;ri++){
scanf("%ld%ld",&a,&b);
for(i=b+1;;i++)
{
if(i%b==0&&i!=a)
{printf("%ld\n",i);
break;}
}
}
}

Answer 1

#include<stdio.h>
main()
{
int ri,repeat;
int i,a,b,c;
scanf("%d",&repeat);
for(ri=1;ri<=repeat;ri++){
scanf("%ld%ld",&a,&b);
for(i=b+1;;i++)
{
/*
这个反例很简单啊，比如 a = 4*b 。你这样找出来的结果肯定是 c=2*b.
这样 a 和 c 的最大公约数是 2*b 而不是 b 了。

比如 a=4, b=1 ，你找到的结果是 c=2,
这是错的。a=4,c=2 的最大公约数是 2 不是 b=1;
正确的结果是 c = 3;
*/
if(i%b==0&&i!=a)
{
printf("%d\n",i);
break;
}
}
}
}
/* 参考程序 1*/
#include <stdio.h>

int main(int argc, char *argv[])
{
int n,a,b,c;
int x,y,i;
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&a,&b);
for(c=2*b;;c++)
{
if(a!=c && c%b==0)
{
// x 为 a 除掉【公约数（不一定是最大公约数）】 b 后的值
x=a/b;
// y 为 c 除掉【公约数（不一定是最大公约数）】 b 后的值
y=c/b;
/*
这里 x 和 y 的【最大公约数】是 n，
a 和 c 的【最大公约数】这时候等于 b*n 。
要使得 a 和 c 的【最大公约数】等于 b, n必须等于 1
也就是 x 和 y 的最大公约数 是 1
*/
for(i=2;i<=x;i++)
{
if(x%i==0&&y%i==0)
{
break;
}
}
// 如果 i>x ,也就是 x 和 y 的最大公约数 是 1
if(i>x)
{
printf("%d\n",c);
break;
}
}
}
}
return 0;
}
/* 参考程序 2*/

#include <stdio.h>
// 欧几里得求最大公约数算法
int gcd(int a,int b)
{
if(a<=b)
{
return gcd(b,a);
}
else
{
if(b==0)
{
return a;
}
else
{
return gcd(b,a%b);
}
}
}
int main(int argc, char *argv[])
{
int n,a,b,c;
int x,y,i;
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&a,&b);
for(c=2*b;;c++)
{
if(a!=c && gcd(a,c)==b)
{
printf("%d\n",c);
break;
}
}
}
return 0;
}