結果
問題 |
No.1946 ロッカーの問題
|
ユーザー |
![]() |
提出日時 | 2022-05-20 21:42:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 288 ms / 3,000 ms |
コード長 | 1,100 bytes |
コンパイル時間 | 208 ms |
コンパイル使用メモリ | 82,384 KB |
実行使用メモリ | 107,396 KB |
最終ジャッジ日時 | 2024-09-20 07:40:10 |
合計ジャッジ時間 | 4,352 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
# Sieve of Eratosthenes class SOE: def __init__(self,m): self.sieve=[-1]*(m+1) self.prime=[] for i in range(2,m+1): if self.sieve[i]==-1: self.prime.append(i) self.sieve[i]=i j=2*i while j<=m: self.sieve[j]=i j+=i def primes(self): # get primes return self.prime def fact(self,n): # prime factorization d={} while n!=1: k=self.sieve[n] if k not in d: d[k]=0 d[k]+=1 n//=k return d def div(self,n): # get divisors c=[1] while n!=1: p=self.sieve[n] cnt=1 n//=p while self.sieve[n]==p: cnt+=1 n//=p s=c.copy() for i in s: for j in range(1,cnt+1): c.append(i*(p**j)) return c soe=SOE(2*10**5+10) n,m=map(int,input().split()) a=list(map(int,input().split())) c=[0]*(n+1) for i in a: c[i]+=1 d=[0]*(n+1) for i in range(1,n+1): for j in soe.div(i): d[j]^=1 ans=0 for i in range(n,0,-1): if c[i]!=d[i]: ans+=1 for j in soe.div(i): d[j]^=1 print(ans)