📚

TOYPRO解説記事 - Coprime(500点)

2 min read

1.概要

競技プログラミングのサイト「TOYPRO」の500点問題、Coprimeの解説をします!
急いで解説を読みたい方は3-3節から読み始めてください。

2.問題

ピッピ君は2つの整数AとBを見つけました。
AをB回掛けた数(AのB乗)と、BをA回掛けた数(BのA乗)が互いに素であるか判定してください。
互いに素な場合はYes、互いに素でない場合はNoと出力してください。
※この問題、制約で5秒以内に実行可能なプログラムは作成可能です。

制約

1 \leqq A, B \leqq 10^9

入力例1

A = 2
B = 5

出力例1

Yes

入力例2

A = 10
B = 8

出力例2

No

3.解説

3-1.誤答例

まず、素朴な解法として実際にA^BB^Aを計算し、その最大公約数が1かどうか判定する方法が考えられます。
この場合、次のようなコードになります。

import math

A = 2
B = 5

if math.gcd(pow(A, B), pow(B, A)) == 1:
    print("Yes")
else:
    print("No")

pow(A, B)A^Bという意味です。
「何だ、これだけで解けるんじゃないか!」と思うかもしれませんが、これ答え合わせをしてみると…?

かなり長い時間待っても答え合わせが終わりません…
何が起こっているのでしょうか…

3-2.計算量について

実はTOYPROでは5秒以上処理に時間がかかる場合、そのプログラムは中断されてしまいます。

この問題の制約では、A, Bの数値が最大で10^9まで与えられることが分かります。
A^Bを計算するとその時点で10^9回計算する必要があり、コンピュータが1秒に処理できる計算回数は大体10^8回ですので、処理に5秒以上時間がかかってしまうことが予想されます。
(2021/04/21 21:50訂正)
そんなことはありませんでした。pow(A, B)の計算量はO(logB)です。(匿名さん、ご指摘ありがとうございます。)

O(x)でx回計算することを表します。
詳しくはけんちょんさんの記事を見てください。
logをまだ学習していない方は「少ない計算回数で実行できるんだな」という認識でOKです。(興味があれば是非調べてみてください。)

log10^9回は約9回ですので、問題がないように思われます。
しかしながら、pow(A, B)の値が非常に大きくなることで処理が低速になってしまい、実行に膨大な時間がかかってしまうということになります。
(最大で10^{9 \times 10^9}という途方もない数値になってしまいます。)
そのため、上の画像のように答え合わせが終わらないという現象が起こってしまうわけです。

そこで、この問題を小さい数値で解くことを考えます。

3-3.想定解

A^BB^Aが互いに素であるか」という問題を言い換えることはできないでしょうか?
実は、互いに素である整数の性質として、以下のようなものがあります。

A, Bが整数であり、n, mが自然数のとき、
AとBが互いに素であるならばA^nとB^mも互いに素である
また、逆にA^nとB^mが互いに素であるならば、AとBも互いに素である

この性質の証明をここですることは解説記事の趣旨から離れてしまうため、省くことにします。(なぜこうなるのか気になる人は「互いに素 性質」と調べると互いに素である整数の性質について書かれた記事がいくつか見つかると思います。)

さて、以上のことを踏まえると、A^BB^Aが互いに素か判定するにはABが互いに素か判定すれば良いということになります。

実装例は以下の通りです。

import math

A = 2
B = 5

if math.gcd(A, B) == 1:
    print("Yes")
else:
    print("No")

4.さいごに

この記事を読んでくださりありがとうございます。
記事の間違いを見つけた場合や、質問がある場合、解説を書いてほしい問題がある場合はスクラップで連絡してくれると嬉しいです。

お詫び

今回の記事では誤った情報を書いてしまいました。
申し訳ありません。
早い段階でご指摘いただき、とてもありがたい限りです。
今後はこのようなことが起こらないよう、より一層気を付けて解説記事を書いていきたいと思います。

Discussion

ログインするとコメントできます