AtCoder Beginner Contest 161 F を Python で

さて，いよいよ最後の F 問題の Python での解説に移ります。コンテスト中は E より F の方が解けてる人が多かったみたいだったので，E を飛ばしてこの問題を見てみたのですが，流石にまったく歯が立ちませんでした😅
でも Atcoder の解説を見て実装できたので，今回もかなり分かりやすいようにかみ砕いて解説していきたいと思います！
それではまずは問題から。

F – Division or Substraction

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

正整数 N が与えられます。

2 以上 N 以下の整数 K を決めて、N が K 未満になるまで次の操作を繰り返し行います。

操作：N が K で割り切れるとき、N を N/K に置き換える。そうでないとき、N を N−K に置き換える。

最終的に N が 1 になるような K の決め方は何通りありますか？

制約

2≤N≤10^12
N は整数

入力

入力は以下の形式で標準入力から与えられる。

N

出力

最終的に N が 1 になるような K の決め方が何通りあるか出力せよ。

解説

N が K で割れるかどうかによらず，最終的に K 未満になるまで K を引き続けた結果が１になればいいのだから，N を K で割れるだけ割った後の値を N’ として，K を引ける回数を m とすると
N’ = K × m + 1
になればよく，２～N の全ての数 K に対して N’ を出し，N’ % K == 1 なるものの個数を出せばよいです。
しかし，これだと N の制約が最大 10^12 であるため，TLE を起こしてしまいます。もう少し試行する K の数を減らすことを考てみましょう。

まずは N が K で割り切れない時を考えてみます。この場合は N が K 未満になるまでただただ N から K を引いていくだけです。m 回 K を引けるとすると，最終的に N が１になるときは，
N = m × K + 1
このように N が記述できますね。この式を変形して
N – 1 = m × K
というようになります。N は２以上の整数なので，左辺は正の整数になります。従って右辺も正の整数 N-1 となり，m と K も正の整数であるから，結局 K は N-1 の約数ということになります。ただし，約数とは言ってももし K が１であったなら，N は 1(=K) 未満になるまで１を引くので，最終的に N は０になってしまい，題意に反してしまいます。

以上の考察から，N が K で割り切れない時は，K が N-1 の１より大きい約数であればよいということになります。

では次に N が K で割り切れる時を考えてみましょう。つまり，K が N の約数の時ですね。このときはまず N を K で割れるだけ割ってそのあと N が K 未満になるまで K を引き続けるという操作になります。
ということで，N を K で割れるだけ割った後の値を N’ とすると，その後 N’ が K 未満になるまで K を引き続けた結果１になればよいので，m 回 K を引き続けることができるとすると
N’ = K × m + 1
となり，結局 N’ を K で割った余りが１になればいいというわけです。

以上より，調べるべきは

N-1 の１以外の約数の個数
N 　の１以外の約数のうち，上記の N’ を K で割った余りが１になるものの個数

となり，２～N の範囲までの全ての整数で試行を行う必要はなく，かなり試行の数は減ります。

あとは実装するだけですが，まずは N-1 と N の約数の列挙が必要です。これについては

tamlog.hateblo.jp

で解説していますので，これを参照してください。
約数を列挙した後は，それぞれの約数の要素から１を取り除きます。
N-1 の約数の個数はこれで出ますが，N の約数については N’ を出して N’を K で割るという試行が必要なので，これを for と while のループで実装してみました。
それでは，解答例を載せておきます。

解答例

n = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

# N-1の約数の列挙
a = make_divisors(n-1)
# Nの約数の列挙
b = make_divisors(n)

# 約数から１を取り除く
a.remove(1)
b.remove(1)

count = len(a)

for k in b:
    # まず１回nをkで割ったものをn_newという変数に入れる
    n_new = n // k
    # n_newをkで割れるだけ割る
    while n_new % k == 0:
        n_new = n_new // k
　　# 最終的にkで割った余りが１ならcountに１を追加
    if n_new % k == 1:
        count += 1

print(count)

どうでしょうか。
F問題とはいえ，そこまで複雑なことをしなくてもコーディングすることができました！
ただ，これをコンテスト中にできるかと言えば・・・😔
もっと頑張るしかないですね（笑）
それでは！

タムログ

プログラミングについての情報発信をしていきます！

AtCoder Beginner Contest 161 F を Python で

問題文

制約

入力

出力

解説

解答例