这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目地址: http://acm.hdu.edu.cn/showproblem.php?pid=2504
看了一下午的线段树,迷糊了,弄个水题来放松下。 思路: a=bk1 c=bk2 又知道a,b,求c a/b=k1, c/b=k2; k1,k2互质,所以只要找到最小的k2,使k2与k1互质就行。
#include
#include
#include
#include
#include
using namespace std;
__int64 gcd(__int64 a, __int64 b)
{
if(a<b)
{
a ^= b;
b ^= a;
a ^= b;
}
if(b == 0)
return a;
return gcd(b, a%b);
}
__int64 a, b, c;
int nCases;
int main()
{
scanf("%d", &nCases;);
while(nCases--)
{
scanf("%I64d %I64d", &a;, &b;);
__int64 k=a/b;
for(int i=2; ; ++i)
if(gcd(k, i) == 1)
{
printf("%I64d\n", i*b);
break;
}
}
return 0;
}