Question

求高手指教 杭电acm-2504题 我的代码如下：

#include<iostream>
using namespace std;
int main()
{
long t=0;
cin>>t;
while(t--)
{
long a=0,b=0;
cin>>a>>b;
long i=2;
a/=b;
while(a%i==0)
{
i++;
}
cout<<b*i<<endl;
}
}

有请高手ac一下，然后能告诉我我的代码出错的地方，谢谢！
链接为：http://acm.hdu.edu.cn/showproblem.php?pid=2504

Answer 1

算法设计有错
问题是寻找与a/b互质的最小的数，而不是非a/b因子的最小的数

追问

难道不是一样的吗？！能否举出一个例子，给几个数据了解一下，谢谢！

追答

两个概念明显不一样啊
比如12 2 求c
按你的做法12/2 = 6因子2，3
你会得出4所以c = 4*2 = 8但12 8最大公约数是4
实际上与6互质的最小数是5所以c = 2*5 = 10

Answer 2

我的ac代码，看下吧
#include<iostream>
#include<cmath>
using namespace std;
int gys(int a,int b)
{
int c;
do
{
c=a%b;
a=b;
b=c;
}while(b!=0);
return a;
}
int main()
{
int a,b,n,c,i;
cin>>n;
for(i=0;i<n;i++)
{
cin>>a>>b;
for(c=1;c<pow(10,6);c++)
{
if(gys(a,c)==b&&c!=b)
break;
}
cout<<c<<endl;
}
return 0;
}

追问

我有ac代码，我就想知道我的思维到底错在哪里了，感觉好纠结！哎！

追答

你选择的那个回答是对的，的确是找互质最小数，而你找的是a/b的因子中的最小数，这题本来就应该逆向回答，它让你求c，那你就穷举法已知c来验证，这样的思维才不容易出错

Answer 3

main函数没有return

追问

我晕，你提交对了没？！难道你加了个return之类的就ac了？！

追答

就这一个地方错了，其他不影响运行，你自己不会测？代码是你的，自己去完成

追问

我擦，我就是知道，而且肯定的测试提交之后才认真对你说！

要不然你照着这个样子，给ac代码啊？！