又见GCD（DDU2504）

编程入门行业动态更新时间:2024-10-27 20:33:07

又见GCD（DDU2504）

Problem Description 有三个正整数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分析：C一定是最大公约数b的整数倍且不等于b代码如下：#include<stdio.h>
#include<string.h>
using namespace std;
int Gcd(int a,int b){  //求a，b的最大公约数 int c;while(b){c=a%b;a=b;b=c;}return a;
}
int main(){int T;scanf("%d",&T);while(T--){int a,b;scanf("%d%d",&a,&b);for(int i=2;;i++){if(b==Gcd(a,b*i)){printf("%d\n",b*i);break;}}}return 0; 
}

更多推荐

又见GCD（DDU2504）

本文发布于:2024-03-07 14:57:06，感谢您对本站的认可！

本文链接:https://www.elefans.com/category/jswz/34/1718133.html