又见GCD(HDU 2504 GCD(最大公约数))
程序员文章站
2022-06-08 14:05:35
...
题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=2504
题面:
思路:
这道题目与正常的求最大公约数的题目又不一样,这里我们是已经两个数的最大公约数和其中一个数字的数值,求另一个数字,那我们一个数字一个数字的遍历来查找这个数和已知的数字的最大公约数等不等于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;
}
}
}
}