当前位置: 代码迷 >> 综合 >> HDOJ--2504又见GCD
  详细解决方案

HDOJ--2504又见GCD

热度:129   发布时间:2023-10-13 22:46:40.0
又见GCD
Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
Submit  Status

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


代码:

#include<stdio.h>
int GCD(int x,int y)
{if(x%y==0)return y;elsereturn GCD(y,x%y);
}
int main()
{int n,a,b,c;scanf("%d",&n);while(n--){scanf("%d%d",&a,&b);for(int i=b+1;;i++){if(GCD(a,i)==b){c=i;break;} }printf("%d\n",c); } return 0;
}