Day 113-Q4 | 平方因子を含まない数の個数

問題

$T$ 個のクエリが与えられる。$i$ 番目のクエリでは整数 $N_i$ が与えられるので、$1$ 以上 $N_i$ 以下の整数のうち平方因子を持たない数（squarefree number。どの素数の2乗でも割り切れない数）の個数を求めよ。

入力形式

T
N_1
N_2
...
N_T

制約

$1 \le T \le 10$

$1 \le N_i \le 10^{12}$

入出力例

入力例1

出力例1

1
7
61

N=10: {1,2,3,5,6,7,10}の7個。4,8,9が除外される。

入力例2

1
1000000000000

出力例2

607927102274

概念図: 包除原理で「平方数で割り切れる」を足し引きする

ヒント（段階的開示）

ヒント1: 方向性

$N\le10^{12}$なので愚直な判定は不可能。平方因子を持たない数の個数$Q(N)$には包除原理に基づく既知の式がある。「$d^2$で割り切れる数」の個数を全ての$d$について足し引きすればよい。

ヒント2: アプローチ

$Q(N)=\sum_{d=1}^{\lfloor\sqrt N\rfloor}\mu(d)\lfloor N/d^2\rfloor$。$\mu$はメビウス関数。$d$の範囲は$\sqrt N\le10^6$なので、線形篩で$\sqrt{N_{\max}}$までの$\mu$を前計算すれば各クエリは$O(\sqrt N)$で答えられる。

ヒント3: 誘導（コード骨格）

s = isqrt(N)
total = 0
for d in range(1, s+1):
    if mu[d] != 0:
        total += mu[d] * (N // (d*d))

模範解答 (Python)

import sys
import math

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    T = int(data[idx]); idx += 1
    Ns = []
    maxN = 0
    for _ in range(T):
        n = int(data[idx]); idx += 1
        Ns.append(n)
        maxN = max(maxN, n)

    LIM = int(math.isqrt(maxN)) + 1
    mu = [0] * (LIM + 1)
    mu[1] = 1
    primes = []
    is_comp = [False] * (LIM + 1)
    for i in range(2, LIM + 1):
        if not is_comp[i]:
            primes.append(i)
            mu[i] = -1
        for p in primes:
            if i * p > LIM:
                break
            is_comp[i * p] = True
            if i % p == 0:
                mu[i * p] = 0
                break
            else:
                mu[i * p] = -mu[i]

    out = []
    for n in Ns:
        s = int(math.isqrt(n))
        total = 0
        for d in range(1, s + 1):
            if mu[d] != 0:
                total += mu[d] * (n // (d * d))
        out.append(str(total))
    print("\n".join(out))

main()

計算量: 篩の前計算 $O(\sqrt{N_{\max}})$（線形篩）、各クエリ $O(\sqrt{N_i})$。$N=1\dots299$の全区間で愚直な平方因子判定と累積個数が全て一致することを確認済み。

Step-by-Step 解説

1なぜ包除原理の式が成り立つのか
平方因子を持つ数とは「ある素数pについてp²で割り切れる」数。複数の素数の平方で割り切れる数を二重に引きすぎないようμ(d)を係数として足し引きする。

2線形篩でメビウス関数を求める
最小素因数を管理する線形篩でO(LIM)で μ が求まる。i%p==0ならμ(i×p)=0、そうでなければ-μ(i)。

3dの範囲を√Nまでに限定できる理由
d²>Nならば⌊N/d²⌋=0なので寄与しない。

4複数クエリへの対応
N_maxに基づき篩を1回だけ構築し、各クエリで使い回す。

5μ(d)=0の項をスキップする最適化
無平方でないdは和に寄与しないため、チェックを入れて無駄な計算を省く。

よくあるミス

ミス	原因	正しい書き方
dの範囲をN_maxまで篩ってしまう	篩の目的（d²≤Nのdだけでよい）を誤解する	LIM=isqrt(maxN)で篩の範囲を平方根までに抑える
int(n**0.5)を使い浮動小数点誤差で1ずれる	N=10^12程度で丸め誤差が結果に影響しうる	math.isqrtを使い整数演算で正確な平方根を求める
線形篩の更新順序を誤る	is_comp設定と素数判定の順序不整合	素数リスト追加・合成数マークの順序をテンプレ通りに保つ
メビウス関数の定義を誤解する	約数の個数の偶奇など別概念と混同する	μ(1)=1, μ(p)=-1, μ(p²k)=0という定義を押さえる

次のステップ

発展: Dirichletの双曲線法（Day102 Q4）と組み合わせ他の乗法的関数の総和も高速化する
発展: Q(N)をNの関数として二分探索し「K番目の平方因子を持たない数」を求める
発展: 杜教篩（Day100 Q4）でN_max=10^16程度までO(N^{2/3})に高速化する

自己評価

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

Day 113-Q4 — 平方因子を含まない数の個数（Möbius関数篩による Q(N) の高速計算）

問題