Day 175-Q4 — 2026-10-11 | min_25 篩（f(p^e) = p xor e の乗法的関数の和を N=10^9 まで）

📋 コピーimport sys
from math import isqrt

MOD = 10**9 + 7


def main():
    n = int(sys.stdin.readline())
    if n == 1:
        print(1)
        return
    r = isqrt(n)
    # 値の集合 { n // i } を、小さい側 lo[v]（v <= r）と大きい側 hi[i] = 値 n // i（i <= r）に分けて持つ
    lo_c = [v - 1 for v in range(r + 1)]                  # v 以下の 2 以上の整数の個数（篩う前）
    lo_s = [v * (v + 1) // 2 - 1 for v in range(r + 1)]   # その和
    hi_c = [0] + [n // i - 1 for i in range(1, r + 1)]
    hi_s = [0] + [(n // i) * (n // i + 1) // 2 - 1 for i in range(1, r + 1)]
    primes = []
    for p in range(2, r + 1):
        if lo_c[p] == lo_c[p - 1]:
            continue                                      # 合成数
        primes.append(p)
        pc, ps = lo_c[p - 1], lo_s[p - 1]                 # p 未満の素数の個数と和
        p2 = p * p
        lim = min(r, n // p2)
        # 大きい側: 値 n//i >= p^2 のもの
        for i in range(1, lim + 1):
            d = i * p
            if d <= r:
                c, s = hi_c[d], hi_s[d]
            else:
                v = n // d
                c, s = lo_c[v], lo_s[v]
            hi_c[i] -= c - pc
            hi_s[i] -= (s - ps) * p
        # 小さい側: v >= p^2 のもの（大きい v から）
        for v in range(r, p2 - 1, -1):
            w = v // p
            lo_c[v] -= lo_c[w] - pc
            lo_s[v] -= (lo_s[w] - ps) * p
    # f(p) = p xor 1: 奇素数は p - 1、p = 2 は 3。素数についての和 F を値の集合の上で表にする
    lo_f = [lo_s[v] - lo_c[v] + (2 if v >= 2 else 0) for v in range(r + 1)]
    hi_f = [0] + [hi_s[i] - hi_c[i] + 2 for i in range(1, r + 1)]
    np_ = len(primes)
    pref = [0] * (np_ + 1)                                 # 最初の k 個の素数での f(p) の和
    for k, p in enumerate(primes):
        pref[k + 1] = pref[k] + (p ^ 1)
    primes.append(r + 1)                                   # 番兵: (r+1)^2 > n

    def S(v, k):
        # 2..v のうち最小素因数が primes[k] 以上の整数 i の f(i) の和
        res = (lo_f[v] if v <= r else hi_f[n // v]) - pref[k]
        t = k
        p = primes[t]
        while p * p <= v:
            q = primes[t + 1]
            qq = q * q
            pe = p
            e = 1
            while pe * p <= v:
                w = v // pe
                if qq > w:                                 # この先は素数だけ: 再帰せずに表から
                    sub = (lo_f[w] if w <= r else hi_f[n // w]) - pref[t + 1]
                else:
                    sub = S(w, t + 1)
                res += (p ^ e) * sub + (p ^ (e + 1))
                pe *= p
                e += 1
            t += 1
            p = q
        return res

    print((S(n, 0) + 1) % MOD)


main()