teratail header banner
teratail header banner
質問するログイン新規登録
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

AtCoder

AtCoderは、日本の競技プログラミングサイト「AtCoder」に関する内容です。

Q&A

解決済

3回答

252閲覧

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

N.hajik

総合スコア7

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

AtCoder

AtCoderは、日本の競技プログラミングサイト「AtCoder」に関する内容です。

0グッド

0クリップ

投稿2025/06/30 15:01

0

0

主文

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}

AtCoderの該当問題

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

N.hajik

2025/06/30 23:51

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

回答3

0

ベストアンサー

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

44 99

投稿2025/06/30 21:25

actorbug

総合スコア2515

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

N.hajik

2025/06/30 23:55

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

0

デバッガは無いのかね。

C++

1#include <iostream> 2#include <cstdint> // int64_t 3#include <algorithm> // std::max / std::min 4 5 6int64_t euclidean(int64_t m, int64_t n) 7{ 8 int64_t a = std::max(m, n); 9 int64_t b = std::min(m, n); 10 11 while (b != 0) 12 { 13 int64_t tmp = a % b; 14 a = b; 15 b = tmp; 16 } 17 return a; 18} 19 20int main() 21{ 22 int64_t m, n; 23 if (std::cin >> m >> n) 24 std::cout << euclidean(m, n) << '\n'; 25 return 0; 26} 27

投稿2025/06/30 15:59

cametan

総合スコア83

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

N.hajik

2025/06/30 23:53

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

0

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

OSコンパイラー
Windows 11Visual Studio 2022
FreeBSD 14.2g++ 15.0.1
FreeBSD 14.2clang++ 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; }

投稿2025/06/30 15:53

hiroki-o

総合スコア1442

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

N.hajik

2025/06/30 23:54

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

2025/07/01 13:09

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.30%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問