問題
正 $N$ 角形の各頂点を $K$ 色のうちの1色で塗る。回転対称なものを同一視したとき、本質的に異なる塗り方の数を $10^9+7$ で割った余りを求めよ。
入力形式
N K制約
$1 \le N \le 10^{18}$
$1 \le K \le 10^9$
入出力例
入力例 1
3 2出力例 1
4正三角形を2色で塗る: 全白・全黒・2白1黒・2黒1白 = 4通り
入力例 2
6 3出力例 2
130ヒント (段階的開示)
ヒント1: 方向性
Burnside補題: 本質的に異なる塗り方 = $\frac{1}{|G|} \sum_{g \in G} |X^g|$。ここで $|X^g|$ = 操作 $g$ で不変な塗り方の数。
ヒント2: アプローチ
正 $N$ 角形の回転群は $N$ 要素。回転 $r^k$ による不変塗り方の数 = $K^{\gcd(N, k)}$。約数でまとめると答え = $\frac{1}{N} \sum_{d|N} \phi(N/d) \cdot K^d$。
ヒント3: 誘導
MOD = 10**9 + 7
def solve(N, K):
divisors = get_divisors(N)
ans = 0
for d in divisors:
phi = euler_totient(N // d)
ans = (ans + phi * pow(K, d, MOD)) % MOD
ans = ans * pow(N % MOD, MOD - 2, MOD) % MOD
return ans模範解答 (Python)
import sys
from math import gcd
MOD = 10**9 + 7
def get_divisors(n):
divs = []
i = 1
while i * i <= n:
if n % i == 0:
divs.append(i)
if i != n // i:
divs.append(n // i)
i += 1
return sorted(divs)
def euler_totient(n):
result = n
temp = n
p = 2
while p * p <= temp:
if temp % p == 0:
while temp % p == 0:
temp //= p
result = result // p * (p - 1)
p += 1
if temp > 1:
result = result // temp * (temp - 1)
return result
def solve():
N, K = map(int, input().split())
divisors = get_divisors(N)
ans = 0
for d in divisors:
phi = euler_totient(N // d)
term = phi % MOD * pow(K % MOD, d % (MOD - 1), MOD) % MOD
ans = (ans + term) % MOD
inv_N = pow(N % MOD, MOD - 2, MOD)
ans = ans * inv_N % MOD
print(ans)
solve()Step-by-Step 解説
1Burnside補題の適用
群 $G$ が集合 $X$ に作用するとき、軌道の数 $|X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|$。
群 $G$ が集合 $X$ に作用するとき、軌道の数 $|X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|$。
2回転 $r^k$ の固定点数
頂点を $0, \ldots, N-1$ とし、$r^k$ は $i \mapsto (i+k) \bmod N$。サイクル数 = $\gcd(N, k)$ なので、固定点数 = $K^{\gcd(N,k)}$。
頂点を $0, \ldots, N-1$ とし、$r^k$ は $i \mapsto (i+k) \bmod N$。サイクル数 = $\gcd(N, k)$ なので、固定点数 = $K^{\gcd(N,k)}$。
3約数でまとめる
$\gcd(N, k) = d$ となる $k$ の個数 = $\phi(N/d)$。よって答え = $\frac{1}{N} \sum_{d|N} \phi(N/d) K^d$。
$\gcd(N, k) = d$ となる $k$ の個数 = $\phi(N/d)$。よって答え = $\frac{1}{N} \sum_{d|N} \phi(N/d) K^d$。
4大きな指数の pow
フェルマーの小定理より指数を $\bmod (p-1)$ に落とせる。
フェルマーの小定理より指数を $\bmod (p-1)$ に落とせる。
5$N$ の逆元
答えを $N$ で割る →
答えを $N$ で割る →
pow(N, MOD-2, MOD)。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 指数 $d$ をそのまま使う | $d > MOD$ でオーバーフロー的誤り | pow(K % MOD, d % (MOD-1), MOD) |
| $N$ 自体を MOD で割ってしまう | N は整数として約数列挙 | get_divisors は整数のまま |
| totient 計算の factor 抜け | 大きい素因数 $p > \sqrt{N}$ を見落とし | if temp > 1: result //= temp * (temp-1) |
次のステップ
- 発展問題: 回転+反転（二面体群）を対称として同一視した塗り方数
- Pólya の計数定理（サイクル指数を用いた一般化）