結果

問題 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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
    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

"""
0