题解 P3653 【小清新数学题】

· · 题解

前言：这题题解太少了叭……？窝码风好康窝来写题解！

观察数据范围发现虽然l,r非常大，但是r-l很小，所以考虑暴力算r-l这一段的。

考虑\mu(x)的最基本定义式：

\mu(x)=\left\{\begin{aligned} 1 \qquad \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x=1 \\ (-1)^k \qquad x=p_1p_2\dots p_k \\ 0 \qquad \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ else \end{aligned}\right.

也就是说\mu(x)只和因子个数有关。

因为l,r\leq 10^{18}，\sqrt n筛因子不太行，而如果写pollard_rho那么要对每个数都做一次，复杂度也无法承受。所以考虑预处理n^\frac{1}{3}以内的因子，因为n除完n^\frac{1}{3}内的因子之后最多只会剩下两个因子。考虑筛出10^6以内的质数，然后去除，除的时候顺便筛\mu。发现剩下的只有这三种情况：

left(x)=\left\{\begin{aligned}p^2 \qquad \ \ \ \ \ \ \ \ \Rightarrow\mu(x)=0 \\ pp'\ \qquad \Rightarrow\mu(x)=\mu(x)\\ p \qquad \ \Rightarrow\mu(x) =-\mu(x)\\\end{aligned}\right.

为什么只会有这三种情况呢？因为x必然只有\gt 10^6的因子，而x\leq 10^{18} ，所以最多只有两个因子。

判断x=p^2直接sqrt，判断x \in prime直接用Millar_Rabin，这两个都判断过了第二种情况就是剩下的。

所以只要筛10^6以内的质数，然后暴力枚举x\in [l,r]判一下再统计就ok了。

\color{#66bbf4}{Code : } 

#include <cstdio>
#include <cmath>
#define it register int
#define ct const int
#define il inline
using namespace std;
typedef long long ll;
#define rll register ll
#define cll const ll
const int N = 1000005;
int p[N], cnt, mu[N], ans;
bool isp[N];
ll l, r, lft[N];
namespace MR {
    const int p[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 };
    il ll mul(cll a, cll b, cll p) {return (a * b - (unsigned long long)((long double)a / p * b + 1e-7) * p + p) % p;}
    il ll ksm(rll x, rll L, cll p) { rll ans = 1; while (L) L& 1 ? ans = mul(ans, x, p) : 0, x = mul(x, x, p), L >>= 1; return ans; }
    il bool isp(cll n) {
        for (it i = 0; i < 14; ++i) if (!(n % p[i])) return n == p[i];
        rll r = n - 1;it pw = 0;
        while (!(r & 1)) r >>= 1, ++pw;
        for (it i = 0, j; i < 14; ++i) {
            rll x = ksm(p[i], r, n), y;
            for (j = 1; j <= pw && x > 1; ++j) {
                y = mul(x, x, n);
                if (y == 1 && x != n - 1) return 0;
                x = y;
            }
            if (x ! = 1) return 0;
        }
        return 1;
    }
} 
il void Pre() {
    it i, j, x;
    for (i = 2; i < N; ++i) {
        if (!isp[i]) p[++cnt] = i;
        for (j = 1; (x = p[j] * i) < N && j < = cnt; ++j) {
            isp[x] = 1;
            if (!(i % p[j])) break;
        }
    }
}
int main() {
    scanf("%lld%lld", &l, &r), Pre(); it i, x, y;
    for (i = r - l, x = 0; x <= i; ++x) lft[x] = x + l, mu[x] = 1;
    for (i = 1; i <= cnt && p[i] <= r; ++i)
        for (rll j = ((l - 1) / p[i] + 1) * p[i]; j <= r; j += p[i]) {
            x = j - l, y = 0;
            while (!(lft[x] % p[i])) lft[x] /= p[i], ++y;
            mu[x] = (y > 1 ? 0 : -mu[x]);
        }
    for (i = r - l, x = 0; x <= i; ++x)
        lft[x] > 1 ? y = (int)sqrt(lft[x]) , mu[x] = (y * y == lft[x] ? 0 : (MR::isp(lft[x]) ? -mu[x] : mu[x])) : 0, ans += mu[x];
    printf("%d", ans);
    return 0;
}