結果

問題 No.8123 Calculated N !
ユーザー KumaTachiRen
提出日時 2025-03-01 23:47:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 413 ms / 2,000 ms
コード長 922 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 82,252 KB
実行使用メモリ 74,996 KB
最終ジャッジ日時 2025-04-01 20:50:13
合計ジャッジ時間 5,697 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

n = int(input())

sq = math.isqrt(n)
large = [0 if i == 0 else n // i - 1 for i in range(sq + 1)]
small = [0 if i == 0 else i - 1 for i in range(n // sq)]
for p in range(2, sq + 1):
	if p < len(small):
		if small[p] <= small[p - 1]: continue
	else:
		if large[n // p] <= small[p - 1]: continue
	c, q = small[p - 1], p * p
	for i in range(1, min(sq, n // q) + 1):
		ip = i * p
		v = (large[ip] if ip < len(large) else small[n // ip]) - c
		if i < len(large): large[i] -= v
		else: small[n // i] -= v
	for i in range(len(small) - 1, q - 1, -1):
		small[i] -= small[i // p] - c

MOD = 1000000007
ans = 1
# n // (i + 1) < p <= n // i
for i in range(1, sq):
    ans = ans * pow(i + 1, large[i] - large[i + 1], MOD) % MOD
# p <= n // sq
small += [large[sq]]
for p in range(2, len(small)):
    if small[p] == small[p - 1]: continue
    x, s = n, 1
    while x > 0: x //= p; s += x
    ans = ans * s % MOD

print(ans)
0