結果
問題 | No.1659 Product of Divisors |
ユーザー | 👑 SPD_9X2 |
提出日時 | 2021-08-27 22:46:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 130 ms / 2,000 ms |
コード長 | 3,049 bytes |
コンパイル時間 | 194 ms |
コンパイル使用メモリ | 82,120 KB |
実行使用メモリ | 96,560 KB |
最終ジャッジ日時 | 2024-05-01 03:31:42 |
合計ジャッジ時間 | 3,863 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 93 ms
84,784 KB |
testcase_01 | AC | 94 ms
85,632 KB |
testcase_02 | AC | 104 ms
86,000 KB |
testcase_03 | AC | 93 ms
85,376 KB |
testcase_04 | AC | 109 ms
85,728 KB |
testcase_05 | AC | 115 ms
93,568 KB |
testcase_06 | AC | 97 ms
85,704 KB |
testcase_07 | AC | 105 ms
85,376 KB |
testcase_08 | AC | 107 ms
85,516 KB |
testcase_09 | AC | 108 ms
88,216 KB |
testcase_10 | AC | 109 ms
88,020 KB |
testcase_11 | AC | 110 ms
85,888 KB |
testcase_12 | AC | 130 ms
96,560 KB |
testcase_13 | AC | 103 ms
85,524 KB |
testcase_14 | AC | 130 ms
96,452 KB |
testcase_15 | AC | 106 ms
85,212 KB |
testcase_16 | AC | 106 ms
85,120 KB |
testcase_17 | AC | 95 ms
85,368 KB |
testcase_18 | AC | 94 ms
85,740 KB |
testcase_19 | AC | 100 ms
85,524 KB |
testcase_20 | AC | 105 ms
87,680 KB |
testcase_21 | AC | 112 ms
87,888 KB |
testcase_22 | AC | 105 ms
88,192 KB |
testcase_23 | AC | 111 ms
87,992 KB |
testcase_24 | AC | 106 ms
88,168 KB |
ソースコード
""" 約数列挙は可能 また、約数の個数は… 割と少ないのでは dpでいける…? dp[x] = 積がxの場合の数 素因数分解? Nは素因数分解でき、 N // x か x自身を素因数分解できるので まぁ可能 定数倍が厳しい可能性はある ?個をN個に分割する方法に関しては前計算可能 Nを素因数分解 Nの約数に関して高速素因数分解 √N * log N まぁ可能かな """ from sys import stdin def modfac(n, MOD): f = 1 factorials = [1] for m in range(1, n + 1): f *= m f %= MOD factorials.append(f) inv = pow(f, MOD - 2, MOD) invs = [1] * (n + 1) invs[n] = inv for m in range(n, 1, -1): inv *= m inv %= MOD invs[m - 1] = inv return factorials, invs def modnCr(n,r,mod,fac,inv): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる) return fac[n] * inv[n-r] * inv[r] % mod def inverse(x,mod): return pow(x,mod-2,mod) def nCr(n,r,mod): u = 1 d = 1 for i in range(r): u *= n-i d *= i+1 u %= mod d %= mod return u * inverse(d,mod) % mod mod = 10**9+7 fac,inv = modfac(500,mod) def Sieve(n): #n以下の素数全列挙(O(nloglogn)) retは素数が入ってる。divlisはその数字の素因数が一つ入ってる ret = [] divlis = [-1] * (n+1) #何で割ったかのリスト(初期値は-1) flag = [True] * (n+1) flag[0] = False flag[1] = False ind = 2 while ind <= n: if flag[ind]: ret.append(ind) ind2 = ind ** 2 while ind2 <= n: flag[ind2] = False divlis[ind2] = ind ind2 += ind ind += 1 return ret,divlis tmp,divlis = Sieve(1000010) def divs(x): ret = {} while divlis[x] != -1: ds = divlis[x] if ds not in ret: ret[ds] = 0 ret[ds] += 1 x //= ds if x != 1: if x not in ret: ret[x] = 0 ret[x] += 1 return ret N,K = map(int,stdin.readline().split()) divx = [1] for i in range(1,200): divx.append( nCr(i+K-1,i,mod) ) #print (divx) pdic = {} TN = N for i in range(2,1000010): if TN % i == 0: pdic[i] = 0 while TN % i == 0: TN //= i pdic[i] += 1 if TN != 1: pdic[TN] = 1 ans = 0 for l in range(1,1000010): if N % l == 0: r = N // l if r < l: break dps = divs(l) nans = 1 for p in dps: nans *= divx[dps[p]] nans %= mod #print (l,nans) ans += nans if r != l: nans = 1 for p in pdic: nox = pdic[p] if p in dps: nox -= dps[p] nans *= divx[nox] nans %= mod #print (r,nans) ans += nans print (ans % mod)