最大公約数を求めるプログラム

Question

主文

1以上10^9以下の整数A,Bが入力されるとき、それらの最大公約数を返すプログラムを作りたいです。ユークリッドの互除法で解ける事は承知ですが、以下のプログラムでできない理由を知りたいです。

背景

AtCoderのアルゴリズムと数学　演習問題集 015の自動採点システムを使うとWA(不正解)になりました。

該当のソースコード

#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;
}

AtCoderの該当問題

Comments

[N.hajik]

以下のコードにして解決しました。
#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;
}

Answer 1

以下の入力例に対し、正しい出力は11ですが、ご提示のコードだと1が返ります。

44 99

Comments

[N.hajik]

回答ありがとうございます。iのデクリメントの位置が間違っていたことに気づけました。解決しましたのでベストアンサーに選ばせていただきます。

Answer 2

デバッガは無いのかね。

#include <iostream>
#include <cstdint>   // int64_t
#include <algorithm> // std::max / std::min


int64_t euclidean(int64_t m, int64_t n)
{
  int64_t a = std::max(m, n);
  int64_t b = std::min(m, n);

  while (b != 0)
    {
      int64_t tmp = a % b;
      a = b;
      b = tmp;
    }
  return a;
}

int main()
{
  int64_t m, n;
  if (std::cin >> m >> n)
    std::cout << euclidean(m, n) << '\n';
  return 0;
}

Comments

[N.hajik]

回答ありがとうございます。解決策ではなく出来ない理由を知りたかったです。

Answer 3

以下の3環境で確認しました。

OS	コンパイラー
Windows 11	Visual Studio 2022
FreeBSD 14.2	g++ 15.0.1
FreeBSD 14.2	clang++ 21.0.0

標準C++17以降なら、std::gcdを使うと楽です。

#include <iostream>
#include <numeric>
typedef long long ll;
using namespace std;

ll A, B;

int main()
{
    cin >> A >> B;
    cout << gcd(A, B) << endl;
    return 0;
}

Comments

[N.hajik]

回答ありがとうございます。std::gcdの中のアルゴリズムを理解するための問題ですので利用しない方がいいと思いました。また、解決策ではなくダメな理由が知りたかったです。

[hiroki-o]

現状のstd::gcd実装より高速なアルゴリズムを発見したら、ぜひGCCかClangに貢献してください。
期待しています。