HDOJ 2504 又见GCD

这篇博客是从旧博客 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;
}