HDOJ 2504 又见GCD

题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2504

看了一下午的线段树,迷糊了,弄个水题来放松下。
思路:
a=b*k1
c=b*k2
又知道a,b,求c
a/b=k1,
c/b=k2;
k1,k2互质,所以只要找到最小的k2,使k2与k1互质就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <cstring>
#include <ctype.h>
#include <stdlib.h>
#include <string>
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;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDOJ 2504 又见GCD》有60个想法

  1. 题目没有说明a和c谁大谁小,那么也就是说当a = 2, b =2和a=4, b = 2的结果一样,但是你这代码不一样;你决定了a < b;

发表评论

电子邮件地址不会被公开。 必填项已用*标注