hdu-またGCDを見て
1097 ワード
hdu-またGCD解題報告を参照
Problem Description
3つの正の整数a,b,c(0
Input
最初の行にはnが入力され、n組のテストデータがあり、次のn行には、各行に2つの正の整数a,bが入力される.
Output
対応するcを出力し、各テストデータが1行を占める.
Sample Input
Sample Output
この問題に穴をあけられた.テーマを見終わって、私の最初の反応はc=2*b.を感じて、そしてすぐにそれを叩いて、結果はwrongになりました.その後、慣性思考が人を殺すことが分かった.a=12、b=2のとき、c=10だった.
だからこの問題の解題の構想は、a/bの値を求めてからiを求めるべきで、(iは条件を満たす最小のa/bとの相互質の数でなければならない).互質、すなわちgcd(a/b,i)=1である.最後の結果はc=i*bである.
Problem Description
3つの正の整数a,b,c(0
Input
最初の行にはnが入力され、n組のテストデータがあり、次のn行には、各行に2つの正の整数a,bが入力される.
Output
対応するcを出力し、各テストデータが1行を占める.
Sample Input
2
6 2
12 4Sample Output
4
8この問題に穴をあけられた.テーマを見終わって、私の最初の反応はc=2*b.を感じて、そしてすぐにそれを叩いて、結果はwrongになりました.その後、慣性思考が人を殺すことが分かった.a=12、b=2のとき、c=10だった.
だからこの問題の解題の構想は、a/bの値を求めてからiを求めるべきで、(iは条件を満たす最小のa/bとの相互質の数でなければならない).互質、すなわちgcd(a/b,i)=1である.最後の結果はc=i*bである.
#include<stdio.h>
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
int n,a,b,i,temp;
scanf("%d",&n);
while(n--)
{
scanf("%d %d",&a,&b);
temp=a/b;
for(i=2;;i++)
{
if(gcd(temp,i)==1)
break;
}
printf("%d
",i*b);
}
return 0;
}