結果
問題 | 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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 45 ms
54,272 KB |
testcase_01 | AC | 46 ms
54,144 KB |
testcase_02 | AC | 45 ms
54,144 KB |
testcase_03 | AC | 44 ms
54,400 KB |
testcase_04 | AC | 44 ms
54,144 KB |
testcase_05 | AC | 43 ms
54,016 KB |
testcase_06 | AC | 45 ms
54,784 KB |
testcase_07 | AC | 57 ms
64,768 KB |
testcase_08 | AC | 58 ms
65,408 KB |
testcase_09 | AC | 64 ms
68,096 KB |
testcase_10 | AC | 64 ms
68,608 KB |
ソースコード
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 & 0x0000007f import 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,deque import bisect import itertools dic = defaultdict(int) d = deque() YN = ['No','Yes'] N,L,R = MI() C = LI() n2 = 2**N dp = [0]*(n2)#少なくともbitが立っている部分では割り切れる奴の個数 import math for i in range(n2): s = 1 for 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)