Blog·Tanky WooABOUTRSS

HDOJ 2504 又见GCD

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