题目传送门
题目分析
杜教筛模板题，人生中第一道杜教筛。
在这里推荐一篇非常棒的文章。【skywalkert’s space】 相信大多数人都是从这里开始了解和学习杜教筛的。
解题方法我就不一条公式一条公式的敲进去了，直接引用该文章中的片段：
其实杜教筛就分为两个主要部分，一个是在所有询问之前的线性筛，预处理出
n23
n
2
3
的表。另一个部分就是在dfs中进行分块计算，同时用哈希或map记忆化搜索。
ps：用hash一般比用map要快，我采用手写hash的做法，代码会略长(我就没写过几次hash)。 还有，一开始我RE到死，原因竟然是有几个地方爆了int(谁叫我作死开int)，要注意处理强转的细节，或者多用long long。
代码
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#define N 1000010
#define M 2333333
using namespace std;
typedef long long LL;
int T, n, cnt;
bool vis[N];
int miu[N], prime[N];
LL phi[N];
int hash_n1[M], hash_n2[M], hash_v2[M];
LL hash_v1[M];
void Da(){
miu[
1] =
1;
vis[
1] =
true;
phi[
1] =
1ll;
for(
int i =
2; i < N; i++){
if(!vis[i]){
prime[++cnt] = i;
miu[i] = -
1;
phi[i] = (LL)(i-
1);
}
for(
int j =
1; j <= cnt && i * prime[j] < N; j++){
vis[i * prime[j]] =
true;
if(i % prime[j] ==
0){
miu[i * prime[j]] =
0;
phi[i * prime[j]] = phi[i] * (LL)prime[j];
break;
}
else{
miu[i * prime[j]] = -miu[i];
phi[i * prime[j]] = phi[i] * (LL)(prime[j]-
1);
}
}
}
for(
int i =
1; i < N; i++) phi[i] += phi[i-
1], miu[i] += miu[i-
1];
}
LL Find1(
int x){
int p = x % M;
while(hash_n1[p] && hash_n1[p] != x) p = (p+
1) % M;
if(!hash_n1[p])
return -
1;
return hash_v1[p];
}
int Find2(
int x){
int p = x % M;
while(hash_n2[p] && hash_n2[p] != x) p = (p+
1) % M;
if(!hash_n2[p])
return -
1;
return hash_v2[p];
}
void Push1(LL v,
int x){
int p = x % M;
while(hash_n1[p]) p = (p+
1) % M;
hash_v1[p] = v;
hash_n1[p] = x;
}
void Push2(
int v,
int x){
int p = x % M;
while(hash_n2[p]) p = (p+
1) % M;
hash_v2[p] = v;
hash_n2[p] = x;
}
LL Sum_Phi(
int x){
if(x < N)
return phi[x];
LL res = Find1(x);
if(~ res)
return res;
else res = (LL)x * ((LL)x+
1) >>
1;
int last;
for(
int i =
2;; i = last+
1){
last = x/(x/i);
res -= (LL)(last-i+
1) * Sum_Phi(x/i);
if(last >= x)
break;
}
Push1(res, x);
return res;
}
int Sum_Miu(
int x){
if(x < N)
return miu[x];
int res = Find2(x);
if(~ res)
return res;
else res =
1;
int last;
for(
int i =
2;; i = last+
1){
last = x/(x/i);
res -= (last-i+
1) * Sum_Miu(x/i);
if(last >= x)
break;
}
Push2(res, x);
return res;
}
int main(){
freopen(
"bzoj3944.in",
"r", stdin);
freopen(
"bzoj3944.out",
"w", stdout);
Da();
scanf(
"%d", &T);
while(T --){
scanf(
"%d", &n);
printf(
"%lld %d\n", Sum_Phi(n), Sum_Miu(n));
}
return 0;
}
