結果

問題 No.990 N×Mマス計算（Kの倍数）
ユーザー persimmon-persimmonpersimmon-persimmon
提出日時 2021-07-01 15:23:47
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,039 bytes
コンパイル時間 1,733 ms
コンパイル使用メモリ 86,932 KB
実行使用メモリ 92,700 KB
最終ジャッジ日時 2023-09-10 12:45:05
合計ジャッジ時間 5,845 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 98 ms
76,252 KB
testcase_01 AC 101 ms
72,220 KB
testcase_02 AC 94 ms
71,812 KB
testcase_03 AC 92 ms
71,748 KB
testcase_04 AC 111 ms
77,096 KB
testcase_05 AC 92 ms
71,400 KB
testcase_06 AC 91 ms
71,816 KB
testcase_07 AC 97 ms
72,584 KB
testcase_08 AC 94 ms
71,612 KB
testcase_09 AC 92 ms
71,652 KB
testcase_10 AC 160 ms
88,276 KB
testcase_11 AC 147 ms
92,700 KB
testcase_12 TLE -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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
    ary[kk]+=1
    keys=list(ary.keys())
    # keys:kの素因数の種類。多くとも9個
    aary=defaultdict(int)
    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(cnt)
      aary[tuple(tmp)]+=1
    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
      for key in aary:
        if not any(u+v<ary[keys[i]] for i,(u,v) in enumerate(zip(tmp,key))):
          ans+=aary[key]
  
    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)
0