結果
問題 | No.1659 Product of Divisors |
ユーザー | 👑 SPD_9X2 |
提出日時 | 2021-08-27 22:46:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 185 ms / 2,000 ms |
コード長 | 3,049 bytes |
コンパイル時間 | 307 ms |
コンパイル使用メモリ | 87,080 KB |
実行使用メモリ | 97,796 KB |
最終ジャッジ日時 | 2023-08-13 10:04:22 |
合計ジャッジ時間 | 5,431 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 142 ms
96,408 KB |
testcase_01 | AC | 151 ms
96,228 KB |
testcase_02 | AC | 161 ms
96,584 KB |
testcase_03 | AC | 139 ms
96,548 KB |
testcase_04 | AC | 157 ms
96,580 KB |
testcase_05 | AC | 183 ms
97,796 KB |
testcase_06 | AC | 151 ms
96,296 KB |
testcase_07 | AC | 152 ms
96,652 KB |
testcase_08 | AC | 155 ms
96,416 KB |
testcase_09 | AC | 157 ms
96,596 KB |
testcase_10 | AC | 154 ms
96,596 KB |
testcase_11 | AC | 157 ms
96,604 KB |
testcase_12 | AC | 184 ms
97,300 KB |
testcase_13 | AC | 157 ms
96,492 KB |
testcase_14 | AC | 185 ms
97,168 KB |
testcase_15 | AC | 158 ms
96,688 KB |
testcase_16 | AC | 157 ms
96,632 KB |
testcase_17 | AC | 143 ms
96,656 KB |
testcase_18 | AC | 148 ms
96,712 KB |
testcase_19 | AC | 155 ms
96,464 KB |
testcase_20 | AC | 159 ms
96,616 KB |
testcase_21 | AC | 162 ms
96,580 KB |
testcase_22 | AC | 155 ms
96,712 KB |
testcase_23 | AC | 163 ms
96,600 KB |
testcase_24 | AC | 173 ms
96,636 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)