結果
問題 | No.1731 Product of Subsequence |
ユーザー |
|
提出日時 | 2021-11-05 21:55:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,324 ms / 2,000 ms |
コード長 | 906 bytes |
コンパイル時間 | 426 ms |
コンパイル使用メモリ | 82,688 KB |
実行使用メモリ | 83,584 KB |
最終ジャッジ日時 | 2024-11-08 04:37:34 |
合計ジャッジ時間 | 11,655 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 31 |
ソースコード
n,k = map(int,input().split())A = list(map(int,input().split()))mod = 10**9+7if k == 1:print((pow(2,n,mod)-1)%mod)exit()div = []dnum = []num = kfor i in range(2,int(k**0.5)+1):if num%i:continuecount = 0while num%i == 0:num //= icount += 1div.append(i)dnum.append(count)if num != 1:div.append(num)dnum.append(1)l = len(div)dic = {k:1}for a in A:cand = [0]*lfor i,d in enumerate(div):while a%d == 0:a //= dcand[i] += 1ndic = {}for x,v in dic.items():nex = xfor i in range(l):for j in range(cand[i]):if nex%div[i] == 0:nex //= div[i]else:breakndic[nex] = (ndic.get(nex,0)+v)%modndic[x] = (ndic.get(x,0)+v)%moddic = ndicprint(dic.get(1,0))