欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

又见GCD(HDU 2504 GCD(最大公约数))

程序员文章站 2022-06-08 14:05:35
...

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=2504

题面:

又见GCD(HDU 2504 GCD(最大公约数))

思路:

这道题目与正常的求最大公约数的题目又不一样,这里我们是已经两个数的最大公约数和其中一个数字的数值,求另一个数字,那我们一个数字一个数字的遍历来查找这个数和已知的数字的最大公约数等不等于b就可以了,注意题目要求另一个数字不等于b。

参考代码:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#include<list>
#include<stacK>
#include<queue>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int a,b;
        cin>>a>>b;
        for(int i=1;; i++)
        {
            if(gcd(i,a)==b&&i!=b)
            {
                cout<<i<<endl;
                break;
            }
        }
    }
}

相关标签: HDU GCD