クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで理解する蟻本「2-6 Carmichael Numbers（UVa No.10006）」(p.114)

Pythonで理解する蟻本（プログラミングコンテストチャレンジブック）

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-6 Carmichael Numbers（UVa No.10006）」(p.114)
のコードをPythonで書き直したものとなっています。

入力


n

入力例1



17

入力例2



561

入力例3



4


2のべき乗の和として表す方法

def mod_pow(x, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * x % mod    # 最下位ビットが立っているときにx^(2^i)を掛ける
        x = x * x % mod        # xを順次二乗していく
        n >>= 1
    return res

再帰関数を使う方法

def mod_pow(x, n, mod):
    if n == 0:
        return 1
    res = mod_pow(x * x % mod, n // 2, mod)
    if n & 1:
        res = res * x % mod
    return res

組み込み関数powを使う方法（重要！）

実は、pythonにはO(log n)でべき乗の計算を行うことができる、pow関数が存在します。

この関数は組み込み関数であるため、インポートせずに使うことができます。

競技プログラミングでべき乗を計算する際には、迷わずこのpow関数を使いましょう。

pow(x, n, mod)

解答

import sys

# 入力
n = int(input())

# 素数判定O(√n)
def is_prime(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return n != 1    # 1の場合は例外

if is_prime(n):
    print('No')
    sys.exit()    # nが素数であれば、'No'を出力してプログラムを終了する

for x in range(2, n):
    if pow(x, n, n) != x:
        print('No')
        sys.exit()    # x^n≡x(mod n) が成り立たないようなxが存在すれば、'No'を出力してプログラムを終了する

print('Yes')