結果
問題 |
No.8123 Calculated N !
|
ユーザー |
![]() |
提出日時 | 2025-04-01 22:26:26 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,275 bytes |
コンパイル時間 | 267 ms |
コンパイル使用メモリ | 82,272 KB |
実行使用メモリ | 82,704 KB |
最終ジャッジ日時 | 2025-04-01 22:26:31 |
合計ジャッジ時間 | 4,932 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 TLE * 1 |
other | -- * 16 |
ソースコード
mod = 1 << 61 - 1 class Prime(): def __init__(self,N): self.N = N self.Is_prime = [1 for i in range(N+1)] self.Is_prime[0] = self.Is_prime[1] = 0 self.P = [] #self.Fact = [[] for i in range(N+1)] ################# #self.Fact[1] = [(1,1)] ################################ for p in range(2,N + 1): if self.Is_prime[p] == 0: continue self.P.append(p) #self.Fact[p].append((p,1)) ########################## for d in range(2,N//p + 1): self.Is_prime[p*d] = 0 q = 1 r = p while (p*d) % (p*r) == 0: q += 1 r *= p #self.Fact[p*d].append((p,q)) ###################### def is_prime(self,p): return self.Is_prime[p] def primelist(self): return self.P def fact(self,n): #########のところを外して使う. return self.Fact[n] P = Prime(400000) def sum_of_multiplicative_function(N): M = 0 while (M + 1) * (M + 1) <= N: M += 1 Q = [i for i in range(1,M + 1)] for i in range(M,0,-1): if Q[-1] == N // i: continue Q.append(N // i) idx = {} for i in range(len(Q)): idx[Q[i]] = i le = len(Q) Sp = [0 for i in range(le)] # Sp_i:1 ~ Q[i] mul = [((1,0))] for a,c in mul: S = [0 for i in range(le)] for i in range(1,le): res = Q[i] # cによって値が違う.(c乗和) S[i] = (res - 1) * a % mod SS = S[:] for x in range(2,M + 1): # not prime if not P.is_prime(x): continue for i in range(le - 1, -1, -1): n = Q[i] if n < x * x: for j in range(i, le): SS[j] = S[j] break S[i] = (S[i] - SS[idx[n // x]] + SS[idx[x - 1]]) % mod for i in range(le): Sp[i] = (Sp[i] + S[i]) % mod return Sp[-1] # N!の約数の個数? Pr = P.P M = len(Pr) mod = 1000000007 inv_2 = (mod + 1) // 2 N = int(input()) n = sum_of_multiplicative_function(N) x = 1 ans = 1 for d in range(2, N + 1): m = sum_of_multiplicative_function(N // d) ans = ans * pow(x + 1, n - m, mod) % mod x += 1 n = m if n < M: break for i in range(n): p = Pr[i] r = 1 + (N // p) + (N // (p * p)) q = p * p while q * p <= N: q *= p r += N // q ans = ans * r % mod print(ans)