結果

問題 No.546 オンリー・ワン
ユーザー lam6er
提出日時 2025-03-20 18:44:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 48 ms / 2,000 ms
コード長 1,741 bytes
コンパイル時間 205 ms
コンパイル使用メモリ 82,192 KB
実行使用メモリ 68,164 KB
最終ジャッジ日時 2025-03-20 18:45:04
合計ジャッジ時間 1,197 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from math import gcd

def main():
    input = sys.stdin.read().split()
    N = int(input[0])
    L = int(input[1])
    H = int(input[2])
    C = list(map(int, input[3:3+N]))
    
    answer = 0
    
    for i in range(N):
        ci = C[i]
        A = H // ci - (L - 1) // ci
        if A <= 0:
            continue
        
        has_one = False
        D = []
        for j in range(N):
            if j == i:
                continue
            cj = C[j]
            g = gcd(ci, cj)
            dj = cj // g
            if dj == 1:
                has_one = True
                break
            D.append(dj)
        
        if has_one:
            continue
        
        m = len(D)
        if m == 0:
            answer += A
            continue
        
        k_start = (L + ci - 1) // ci
        k_end = H // ci
        if k_start > k_end:
            continue
        
        B = 0
        for mask in range(1, 1 << m):
            bits = bin(mask).count('1')
            current_lcm = 1
            valid = True
            for idx in range(m):
                if mask & (1 << idx):
                    d = D[idx]
                    g = gcd(current_lcm, d)
                    new_lcm = (current_lcm // g) * d
                    if new_lcm > k_end:
                        valid = False
                        break
                    current_lcm = new_lcm
            if not valid:
                continue
            cnt = (k_end // current_lcm) - ((k_start - 1) // current_lcm)
            if cnt > 0:
                if bits % 2 == 1:
                    B += cnt
                else:
                    B -= cnt
        answer += (A - B)
    
    print(answer)

if __name__ == "__main__":
    main()
0