主文
1以上10^9以下の整数A,Bが入力されるとき、それらの最大公約数を返すプログラムを作りたいです。ユークリッドの互除法で解ける事は承知ですが、以下のプログラムでできない理由を知りたいです。
背景
AtCoderのアルゴリズムと数学 演習問題集 015の自動採点システムを使うとWA(不正解)になりました。
該当のソースコード
C++
1#include <iostream> 2typedef long long ll; 3using namespace std; 4 5ll A, B; 6ll sN; 7ll bN; 8 9int main(){ 10 cin >> A >> B; 11 ll Ans = 1; 12 if(A <= B){sN = A;bN = B;} 13 else{sN = B; bN = A;} 14 //cout << "sN=" << sN << " bN=" << bN << endl; 15 for(ll i = 2;i * i <= sN;i++){ 16 if(sN % i == 0){ 17 sN /= i; 18 if(bN % i == 0){ 19 bN /= i; 20 Ans *= i; 21 i--; 22 } 23 } 24 } 25 if(sN != 1 and bN % sN == 0){ 26 Ans *= sN; 27 } 28 cout << Ans; 29 return 0; 30}
以下のコードにして解決しました。
#include <iostream>
typedef long long ll;
using namespace std;
ll A, B;
ll sN;
ll bN;
int main(){
cin >> A >> B;
ll Ans = 1;
if(A <= B){sN = A;bN = B;}
else{sN = B; bN = A;}
//cout << "sN=" << sN << " bN=" << bN << endl;
for(ll i = 2;i * i <= sN;i++){
if(sN % i == 0){
sN /= i;
if(bN % i == 0){
bN /= i;
Ans *= i;
}
i--;
}
}
if(sN != 1 and bN % sN == 0){
Ans *= sN;
}
cout << Ans;
return 0;
}

回答3件
あなたの回答
tips
プレビュー