結果

問題 No.990 N×Mマス計算（Kの倍数）
コンテスト
ユーザー persimmon-persimmon
提出日時 2021-07-01 15:23:47
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,039 bytes
コンパイル時間 165 ms
コンパイル使用メモリ 82,316 KB
実行使用メモリ 99,972 KB
最終ジャッジ日時 2024-06-28 04:03:37
合計ジャッジ時間 4,635 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 10 TLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

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