結果
問題 | No.546 オンリー・ワン |
ユーザー | タコイモ |
提出日時 | 2023-03-01 21:58:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 64 ms / 2,000 ms |
コード長 | 1,698 bytes |
コンパイル時間 | 159 ms |
コンパイル使用メモリ | 82,632 KB |
実行使用メモリ | 68,608 KB |
最終ジャッジ日時 | 2024-09-16 19:04:09 |
合計ジャッジ時間 | 1,446 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 7 |
ソースコード
def popcount(x):'''xの立っているビット数をカウントする関数(xは64bit整数)'''# 2bitごとの組に分け、立っているビット数を2bitで表現するx = x - ((x >> 1) & 0x5555555555555555)# 4bit整数に 上位2bit + 下位2bit を計算した値を入れるx = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごとx = x + (x >> 8) # 16bitごとx = x + (x >> 16) # 32bitごとx = x + (x >> 32) # 64bitごと = 全部の合計return x & 0x0000007fimport sys#sys.setrecursionlimit(500000)def I(): return int(sys.stdin.readline().rstrip())def MI(): return map(int,sys.stdin.readline().rstrip().split())def TI(): return tuple(map(int,sys.stdin.readline().rstrip().split()))def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))def S(): return sys.stdin.readline().rstrip()def LS(): return list(sys.stdin.readline().rstrip())#for i, pi in enumerate(p):from collections import defaultdict,dequeimport bisectimport itertoolsdic = defaultdict(int)d = deque()YN = ['No','Yes']N,L,R = MI()C = LI()n2 = 2**Ndp = [0]*(n2)#少なくともbitが立っている部分では割り切れる奴の個数import mathfor i in range(n2):s = 1for j in range(N):if (1<< j)& i:cj = C[j]s = (s*cj)//math.gcd(s,cj)dp[i] = (R//s - (L+s-1)//s)+1#すべての和集合*N-iを除いた和集合S = [0]*(N)ans = 0#print(dp)for i in range(1,n2):x = popcount(i)ans += dp[i]*((-1)**(x+1))for j in range(N):if not (1<< j)& i:S[j] += -dp[i]*((-1)**x)print(ans*N-sum(S))#print(S,ans)