机房墙上贴了点什么抽象的东西
-
正中央贴了个大横幅：英雄不问年少，强国有我少年
-
顺口溜(long long版)
加称左移要强转，赋值传参类型对。
快速幂，光速模，中间量，返回值。
查找类型不怕累，否则爆零两行泪
-
顺口溜(挖坑版)
编译选项文件名，时间空间注意盯
数据范围要看清，注意long long特判0
明题意，膜样例，算效率，主定理
减法取模小心锅，size运算小心负
多测数组要清空，边数计数要置0
算法边界要当心，水过样例喜爆零
推歌：绝体绝命/洛天依 by 阿良良木建
今天哼歌的时候哼绝体绝命哼串了，串到了隔壁 \(\text{miku}\) 的 \(\text{snooze}\) 里
大概就是这样串的
来来 我最亲爱的朋友，来看我毁灭毁灭
请让我去自受自虐承受这污点，反复鞭笞我的罪一遍又一遍
来来 我最牵挂的朋友，请为我悼念悼念
我身上恶疾已蔓延无尽的繁衍，这世界我已厌倦
请别将我救援
[间奏]
つまらなくなった戦争
結局他人が怖いの
液晶に写った量子論が
どんな未来を勝者に選んで
好像还挺搭(绷)
杜教筛
数论函数
比如大家熟知的 \(\mu\) \(\varphi\) 等
积性函数：对于积性函数 \(f\)，已知 \(f(1)=1\) 且对于任意的两个互质的正整数 \(p,q\) 都满足 \(f(p\cdot q)=f(p)\cdot f(q)\)，则称 \(f\) 是积性函数(有的不互质也行，叫做完全积性函数)
常见的积性函数有
\(
\begin{cases}
\mu(n)\\
\varphi(n)\\
d(n)~~(d(n)=\sum_{d|n}1)\\
\sigma(n)~~(\sigma(n)=\sum_{d|n}d)
\end{cases}
\)
一些常见的完全积性函数
\(
\begin{cases}
\epsilon(n)~~(\epsilon(n)=[n=1])\\
\text I(n)~~(\text I(n)=1)\\
\text {id}(n)~~(\text {id}(n)=n)
\end{cases}
\)
狄利克雷卷积
定义数论函数\(f,g\)的卷积为 \(f*g=\sum\limits_{d|n}f(d) \cdot g(\frac{n}{d})\) 其中 \(n\) 是范围
狄利克雷卷积满足以下运算规律
-
交换律(\(f*g=g*f\))；
-
结合律(\((f*g)*h=f*(g*h)\))；
-
分配律(\((f+g)*h=f*h+g*h\))；
把莫比乌斯反演推出来的性质(至少我没推)
这个性质转化成狄利克雷卷积的形式就是
众所周知，\(\varphi\)也有个性质
将它表示成狄利克雷卷积的形式就是
所以可以借此推出人尽皆知的\(\mu\)与\(\varphi\)的关系
你说得对但是这个是人尽皆知的性质
杜教筛
杜教筛是非常好的筛子，能用低于线性的复杂度计算积性函数的前缀和
也就是需要计算$$S(n)=\sum_{i=1}^{n}f(i)$$
算法思想
想办法构造一个\(S(n)\)关于\(S(\lfloor \frac{n}{i}\rfloor)\)的递推式
定理：对于任何一个数论函数\(g\)必定满足
证明
那就可以得到非常好的递推式
按理说只要一个非常好的数论函数\(j\)使
-
可以快速计算\(\sum\limits_{i=1}^{n}(f*g)(i)\)
-
可以快速计算 \(g\) 的单点值好用数论分块求解\(\sum\limits_{i=2}^{n}(f*g)S(\lfloor\frac ni\rfloor)\)
那么就能较短时间求解\(g(1)S(n)\)
- 求\(S(n)=\sum\limits_{i=1}^{n}\mu(i)\)
众所周知，\(\mu * \text I = \epsilon\)，只要选取 \(g=\text I\) 带入上面的式子\(\sum\limits_{i=1}^{n}(f*g)(i)-\sum\limits_{i=2}^{n}g(i)S(\lfloor \frac ni\rfloor)\) 就可以得到
- 求\(S(n)=\sum\limits_{i=1}^{n}\varphi(i)\)
根据一个人尽皆知的卷积公式 \(\varphi*\text I=\text{id}\)
我们可以猜到选取的积性函数也是\(g=\text I\)
那么带入得到的就是
前面的用等差数列求和公式就行，后面的整除分块
但是有一个非常好的方法来筛\(\varphi\)
通过莫比乌斯函数！
那么这是一份杜教筛的板子
点击查看代码
#include<bits/stdc++.h>
inline int read(){
int x=0,f=1,ch=getchar();
while(!isdigit(ch)) { if(ch == '-') f = -f; ch = getchar(); }
while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
#define int long long
#define cin std::cin
#define cout std::cout
#define swap std::swap
#define map std::map
#define string std::string
const char endl='\n';
const int maxn=2000010;
int T,n,pri[maxn],cur,mu[maxn],Mu[maxn];
bool vis[maxn];
map<int,int> mapp;
inline int S_mu(int x){
if(x<maxn) return Mu[x];
if(mapp[x]) return mapp[x];
int ret=1;
for(int i=2,j;i<=x;i=j+1){
j=x/(x/i);
ret-=S_mu(x/i)*(j-i+1);
}
return mapp[x]=ret;
}
inline int S_phi(int x){
int ret=0,j;
for(int i=1;i<=x;i=j+1){
j=x/(x/i);
ret+=(S_mu(j)-S_mu(i-1))*(x/i)*(x/i);
}
return (ret-1)/2+1;
}
inline void pre(){
mu[1]=1;
for(int i=2;i<maxn;i++){
if(!vis[i]){
pri[++cur]=i;
mu[i]=-1;
}
for(int j=1;j<=cur&&i*pri[j]<maxn;j++) {
vis[i*pri[j]]=1;
if(i%pri[j])
mu[i*pri[j]]=-mu[i];
else{
mu[i*pri[j]]=0;
break;
}
}
}
for(int i=1;i<maxn;i++)
Mu[i]=Mu[i-1]+mu[i];
}
signed main() {
pre();T=read();
while(T--){
n=read();
cout<<S_phi(n)<<" "<<S_mu(n)<<endl;
}
}
