又见GCD HDU 2504
程序员文章站
2022-05-17 20:31:54
...
My blog https://dyingdown.github.io/
又见GCD
Problem
有三个正整数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
Analysis
已知gcd(a, c) = b 的值, 求最小的c。
因为c不等于b,所以c从2b开始,依次加b。
Code
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t --){
int m, n;
cin >> m >> n;
int i;
for(i = n * 2; ; i += n){
if(__gcd(m, i) == n){
break;
}
}
cout << i << endl;
}
return 0;
}
上一篇: VB菜单项怎么添加图片?
下一篇: 学习vue3