結果

問題 No.1039 Project Euler でやれ
ユーザー maspymaspy
提出日時 2020-04-24 23:42:24
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,301 bytes
コンパイル時間 270 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 44,208 KB
最終ジャッジ日時 2024-11-08 02:59:59
合計ジャッジ時間 13,796 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample RE * 2
other RE * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
from functools import lru_cache
MOD = 10 ** 9 + 7
U = 10 ** 3 + 10
is_prime = np.zeros(U, np.bool)
is_prime[2] = 1
is_prime[3::2] = 1
for p in range(3, U, 2):
if p * p >= U:
break
if is_prime[p]:
is_prime[p * p:: p + p] = 0
primes = np.where(is_prime)[0]
def cumprod(A, MOD=MOD):
L = len(A)
Lsq = int(L**.5 + 1)
A = np.resize(A, Lsq**2).reshape(Lsq, Lsq)
for n in range(1, Lsq):
A[:, n] *= A[:, n - 1]
A[:, n] %= MOD
for n in range(1, Lsq):
A[n] *= A[n - 1, -1]
A[n] %= MOD
return A.ravel()[:L]
def make_fact(U, MOD=MOD):
x = np.arange(U, dtype=np.int64)
x[0] = 1
fact = cumprod(x, MOD)
fact.flags.writeable = False
return fact
def factor(M):
pf = primes[M % primes == 0]
for p in pf:
e = 0
while M % p == 0:
M //= p
e += 1
yield (int(p), e)
if M > 1:
yield (int(M), 1)
@lru_cache(None)
def GL(p, n):
# count the element of GL(n,F_p)
x = 1
for i in range(n):
x *= (p ** n - p ** i)
x %= MOD
return x % MOD
def Aut(p, e, partition):
# count Aut(prod Z/p^{n_i})
x = 1
smaller = 0
for i in range(1, e + 1):
n = sum(k == i for k in partition)
x *= GL(p, n)
x *= pow(p, (i - 1) * n * n, MOD)
x *= pow(p, smaller * n, MOD)
m = sum(k > i for k in partition)
x *= pow(p, i * m * n, MOD)
smaller += n * i
return x % MOD
def make_partitions(N, largest=None):
if N == 0:
yield []
return
if largest is None:
largest = N
if largest > N:
largest = N
for i in range(largest, 0, -1):
for p in make_partitions(N - i, i):
yield p + [i]
def compute_p_part(p, e):
# sum(1 / Aut)
x = 0
for par in make_partitions(e):
aut = Aut(p, e, par)
x += pow(aut, MOD - 2, MOD)
x %= MOD
return x
def solve(M):
fact = make_fact(M + 10)
x = 1
for p, e in factor(M):
x *= compute_p_part(p, e)
x %= MOD
x *= fact[M]
return x % MOD
M = int(read())
print(solve(M))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0