C-またGCD
648 ワード
C-またGCD
HPU特別訓練(-1)GCD&&素ふるい&&快速べき乗___C-またGCD
3つの正の整数a,b,c(0 Inputの最初の行はnを入力し、n組のテストデータがあることを示し、次のn行は、各行に2つの正の整数a,bを入力する。Outputは対応するcを出力し,各テストデータが1行を占める. Sample Input 2 6 2 12 4 Sample Output 4 8 /* 考え方は簡単です。 b=gcd(a,c)が成立するか否かを判断すればよい この条件を満たすには、次の手順に従います。 c>b;(c!=b切bはcの約数)であるべきである。 だからcは2 b,3 b,4 bであるべきだ.....b=gcd(a,c)まで判断した。 */ #include int gcd(int a,int c) { return !c?a:gcd(c,a%c); } int main() { int a,b,t; scanf("%d",&t); while(t--) { scanf("%d %d",&a,&b); int c=b*2; while(b!=gcd(a,c)) { c+=b; } printf("%d",c); } return 0; }
HPU特別訓練(-1)GCD&&素ふるい&&快速べき乗___C-またGCD
3つの正の整数a,b,c(0 Inputの最初の行はnを入力し、n組のテストデータがあることを示し、次のn行は、各行に2つの正の整数a,bを入力する。Outputは対応するcを出力し,各テストデータが1行を占める. Sample Input 2 6 2 12 4 Sample Output 4 8 /* 考え方は簡単です。 b=gcd(a,c)が成立するか否かを判断すればよい この条件を満たすには、次の手順に従います。 c>b;(c!=b切bはcの約数)であるべきである。 だからcは2 b,3 b,4 bであるべきだ.....b=gcd(a,c)まで判断した。 */ #include int gcd(int a,int c) { return !c?a:gcd(c,a%c); } int main() { int a,b,t; scanf("%d",&t); while(t--) { scanf("%d %d",&a,&b); int c=b*2; while(b!=gcd(a,c)) { c+=b; } printf("%d",c); } return 0; }