首页 > 代码库 > 又见GCD
又见GCD
有三个正整数a,b,c(0<a,b,c<10^6),其中c不等于b。若a和c的最大公约数为b,现已知a和b,求满足条件的最小的c。
Input第一行输入一个n,表示有n组测试数据,接下来的n行,每行输入两个正整数a,b。
Output输出对应的c,每组测试数据占一行。
Sample Input
2 6 2 12 4
Sample Output
4 8
直接用暴力法就好
1 #include<bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 6 int n; 7 cin>>n; 8 int a,b,c; 9 while(n--) 10 { 11 cin>>a>>b; 12 for(c=1;;c++) //注意有两个逗号 13 { 14 if(c!=b&&b==__gcd(a,c)) //若要单独定义“__gcd()”则用头文件“#include<algorithm” 15 { 16 cout<<c<<endl; 17 break; 18 } 19 } 20 } 21 return 0; 22 }
又见GCD
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。