結果
問題 | No.990 N×Mマス計算(Kの倍数) |
ユーザー | persimmon-persimmon |
提出日時 | 2021-07-01 16:16:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 566 ms / 2,000 ms |
コード長 | 3,605 bytes |
コンパイル時間 | 157 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 114,108 KB |
最終ジャッジ日時 | 2024-06-28 05:16:23 |
合計ジャッジ時間 | 4,156 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 46 ms
54,656 KB |
testcase_01 | AC | 47 ms
54,400 KB |
testcase_02 | AC | 48 ms
55,040 KB |
testcase_03 | AC | 48 ms
54,912 KB |
testcase_04 | AC | 53 ms
61,312 KB |
testcase_05 | AC | 48 ms
55,040 KB |
testcase_06 | AC | 50 ms
54,400 KB |
testcase_07 | AC | 49 ms
55,040 KB |
testcase_08 | AC | 48 ms
54,528 KB |
testcase_09 | AC | 48 ms
54,656 KB |
testcase_10 | AC | 124 ms
86,400 KB |
testcase_11 | AC | 118 ms
91,648 KB |
testcase_12 | AC | 563 ms
91,948 KB |
testcase_13 | AC | 130 ms
86,400 KB |
testcase_14 | AC | 143 ms
87,552 KB |
testcase_15 | AC | 119 ms
80,000 KB |
testcase_16 | AC | 142 ms
89,272 KB |
testcase_17 | AC | 109 ms
80,000 KB |
testcase_18 | AC | 566 ms
92,204 KB |
testcase_19 | AC | 288 ms
85,120 KB |
testcase_20 | AC | 193 ms
114,108 KB |
ソースコード
def main0(n,m,k,op,a,b): ans=0 for i in range(n): for j in range(m): if op=="+": if (a[i]+b[j])%k==0: ans+=1 else: if (a[i]*b[j])%k==0: ans+=1 return ans # 指定した整数以下の素数を列挙。エラトステネスの篩 def eratosthenes(n): l0=list(range(2,n+1)) l1=[1]*(n+1) l1[0]=0 l1[1]=0 for li in l0: if li>int(n**0.5): break if l1[li]==1: k=2 while k*li<=n: l1[k*li]=0 k+=1 ret=[i for i,li in enumerate(l1) if li==1] return ret from collections import Counter,defaultdict def main1(n,m,k,op,a,b): if k==1:return m*n if op=="+": ca=dict(Counter([x%k for x in a])) cb=dict(Counter([x%k for x in b])) ans=0 for key,value in ca.items(): if (k-key)%k in cb: ans+=cb[(k-key)%k]*value return ans else: ans=0 aa=[x for x in a if x%k!=0] bb=[x for x in b if x%k!=0] nn=len(aa) mm=len(bb) ans=(n-nn)*m + n*(m-mm) - (n-nn)*(m-mm) kary=eratosthenes(int(k**.5)+1) ary=defaultdict(int) kk=k for x in kary: while kk%x==0: ary[x]+=1 kk//=x if kk==1:break del kary if kk>1: ary[kk]+=1 keys=list(ary.keys()) # keys:kの素因数の種類。多くとも9個 aary=defaultdict(int) # aの要素をkeysの素因数の個数で分類。パターンは1000を超えることもある。 for x in aa: tmp=[] for key in keys: cnt=0 while x%key==0 and cnt<ary[key]: cnt+=1 x//=key tmp.append(ary[key]-cnt) # 要素xをkの倍数にするのに必要な最小構成 aary[tuple(tmp)]+=1 dary=defaultdict(int) for key,value in aary.items(): allpat=[list(key)] for i in range(len(keys)): nallpat=[] for j in range(key[i],ary[keys[i]]+1): for v in allpat: v[i]=j nallpat.append(v[:]) allpat=nallpat #print(allpat) for v in allpat: dary[tuple(v)]+=value #print(keys,ary) #print(aary) #print(dary) for x in bb: tmp=[] for key in keys: cnt=0 while x%key==0 and cnt<ary[key]: cnt+=1 x//=key tmp.append(cnt) if all(y==0 for y in tmp):continue ans+=dary[tuple(tmp)] return ans if __name__=='__main__': n,m,k=map(int,input().split()) b=list(input().split()) op=b[0] b=list(map(int,b[1:])) a=[int(input()) for _ in range(n)] ret1=main1(n,m,k,op,a,b) print(ret1) exit() ret0=main0(n,m,k,op,a,b) print(ret0) from random import randint if __name__=='__main__1': for _ in range(100): n=randint(1,10) m=randint(1,10) k=randint(1,100) a=[randint(1,100) for _ in range(n)] b=[randint(1,100) for _ in range(m)] ret1=main1(n,m,k,"+",a,b) ret0=main0(n,m,k,"+",a,b) if ret1!=ret0: print(n,m,k) print(*["+"]+b) print(*a,sep='\n') print((ret0,ret1)) break ret1=main1(n,m,k,"*",a,b) ret0=main0(n,m,k,"*",a,b) if ret1!=ret0: print(n,m,k) print(*["*"]+b) print(*a,sep='\n') print(_,(ret0,ret1)) break if __name__=='__main__1': ans=0 for _ in range(3000): k=randint(9*10**8,10**9) kary=eratosthenes(int(k**.5)+1) ary=defaultdict(int) kk=k for x in kary: while kk%x==0: ary[x]+=1 kk//=x if kk==1:break ary[kk]+=1 tmp=1 for key,value in ary.items(): tmp*=value+1 ans=max(ans,tmp) print(ans) """ 2,3,5,7=210 12,70 210%12=6 216 204 """