Day 008-Q5 | 包除原理

問題

1 から $N$ までの整数の中で、$K$ 個の素数 $p_1, p_2, \ldots, p_K$ のいずれかで割り切れる整数の個数を求めよ。

制約

$1 \le N \le 10^{18}$

$1 \le K \le 20$

$2 \le p_i \le 10^9$、素数、互いに異なる

入出力例

入力例 1

20 2
2 3

出力例 1

入力例 2

100 3
2 3 5

出力例 2

ヒント (段階的開示)

ヒント1: 方向性

包除原理。$|A \cup B| = |A| + |B| - |A \cap B|$。

ヒント2: アプローチ

$2^K$ 通りの部分集合に対して、その素数の積の倍数の個数を足し引きする。サイズ奇数なら加算、偶数なら減算。

ヒント3: 誘導

for mask in range(1, 1 << K):
    product = 1
    bits = bin(mask).count('1')
    for i in range(K):
        if mask >> i & 1:
            product *= primes[i]
            if product > N: break
    ...

模範解答 (Python)

import sys
input = sys.stdin.readline

def solve():
    N, K = map(int, input().split())
    primes = list(map(int, input().split()))

    result = 0

    for mask in range(1, 1 << K):
        product = 1
        bits = bin(mask).count('1')
        overflow = False

        for i in range(K):
            if mask >> i & 1:
                product *= primes[i]
                if product > N:
                    overflow = True
                    break

        if overflow:
            continue

        count = N // product
        if bits % 2 == 1:
            result += count
        else:
            result -= count

    print(result)

solve()

Step-by-Step 解説

1包除原理の適用
$|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2| = N/p_1 + N/p_2 - N/(p_1 p_2)$。

2ビットマスクによる部分集合列挙
mask の各ビットが素数の含有を表す。popcount で符号を決める。

3積のオーバーフロー対策
積が $N$ を超えたら、その積の倍数は存在しないのでスキップ。

よくあるミス

ミス	原因	正しい書き方
積のオーバーフロー	$N$ 超えで N//product が 0	`if product > N: break`
符号の混同	奇数→加算、偶数→減算	`bits % 2 == 1` で加算
mask=0 を含めてしまう	空集合を数える	`range(1, 1<<K)` で除外

次のステップ

発展問題: $N$ 以下で $K$ 個の素数のどれとも互いに素な整数の個数

自己評価

完全理解おおむね理解要復習

Day 008-Q5 — 包除原理

問題

制約