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