杜教筛用来解决积性函数求前缀和的问题。
复杂度为(O(n^frac{2}{3}))
适用情况：
已知函数(f)，求(sum f)，
存在(f*g=F)，且(g,sum g,F,sum F)容易求出。
常用公式：
(mu*I=[n=1])
(varphi*I=id)
以求(sum mu)为例。
[mu*I=[n=1] \
sum_{i = 1}^{n}[i = 1] = 1 \
1 = sum_{i = 1}^{n}[i = 1]
]
构造出所求函数(mu)
[1 = sum_{i = 1}^{n} sum_{d | i}mu(d) \
]
设(t=i/d)
[1 = sum_{t = 1}^{n} sum_{d = 1}^{lfloor frac{n}{t}
floor} mu(d) \
]
设(M(lfloor frac{n}{t} floor) = sumlimits_{d = 1}^{lfloor frac{n}{t} floor} mu(d))$
[1 = sum_{t = 1}^{n} M(lfloor frac{n}{t}
floor) \
M(n) = 1 - sum_{t = 2}^{n} M(lfloor frac{n}{t}
floor)
]
对于(i<10^7)，可以预处理出(M(i))的值，存到数组里。
比较大的数可以通过数论分块递推求解。
注意：
- 空间限制
- 计算(f(x))时，因为需要递归，不能把(ans)开成全局变量！
(code)
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define MogeKo qwq
using namespace std;
const int maxn = 1e7+5;
const int mod = 999979;
long long a,b;
int prime[5000005],mu[maxn],M[maxn];
int head[mod],nxt[1000005];
int cnt,tot;
pair <long long,long long> num[1000005];
bool vis[maxn],flag;
void Prime() {
M[1] = mu[1] = 1;
for(int i = 2; i <= 10000000; i++) {
if(!vis[i]) {
mu[i] = -1;
prime[++tot] = i;
}
for(int j = 1; j <= tot && i*prime[j] <= 10000000; j++) {
vis[i*prime[j]] = true;
if(i % prime[j] == 0) break;
else mu[i*prime[j]] = -mu[i];
}
M[i] = M[i-1] + mu[i];
}
}
void add(long long key,long long val) {
int x = key % mod;
num[++cnt] = make_pair(key,val);
nxt[cnt] = head[x];
head[x] = cnt;
}
long long query(long long key) {
int x = key % mod;
for(int i = head[x]; i; i = nxt[i])
if(num[i].first == key) {
flag = true;
return num[i].second;
}
return 0;
}
long long f(long long x) {
if(x <= 10000000) return M[x];
flag = false;
long long ans = query(x);
if(flag) return ans;
for(long long i = 2,r; i <= x; i = r+1) {
r = x/(x/i);
ans += (r-i+1) * f(x/i);
}
ans = 1 - ans;
add(x,ans);
return ans;
}
int main() {
scanf("%lld%lld",&a,&b);
Prime();
printf("%lld",f(b)-f(a-1));
return 0;
}