线性素数筛
https://www.luogu.com.cn/problem/P3383
板子
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e8+1000;
int t,p[maxn],k,q;
bool vis[maxn];
void make_prime(ll n){
fill(vis,vis+n,0);
ll cnt=0;
for(int i=2;i<=n;i++){
if(!vis[i]) p[++cnt]=i;
for(int j=1;p[j]*i<=n&&j<=cnt;j++){
vis[p[j]*i]=1;
if(i%p[j]==0) break;
}
}
}
int main(){
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>t>>q;
make_prime(t);
while(q--){
cin>>k;
cout<<p[k]<<endl;
}
return 0;
}
欧拉函数
定义：
$\varphi \left( x \right) $即为小于$x$的所有与$x$互质的整数的个数。
朴素单个欧拉函数值求法：
ll euler(ll n){
ll res=n;
for(ll i=2;i*i<=n;i++){
if(n%i==0){
res-=res/i;
while(n%i==0)
n/=i;
}
}
if(n>1) res-=res/n;
return res;
}
每次遇到可以整除$n$的数就从答案中减去所有该数的倍数，并对$n$进行调整。考虑到当$n$为质数时，整体的复杂度为$O\left( \sqrt{n} \right) $。
相关定理：
1.当$p$为质数时，$\varphi \left( p \right) =p-1$，显然。
2.若$p$为质数，且$n=p^k$，则$\varphi \left( n \right) =p^k-p^{k-1}$。
3.欧拉函数为积性函数(我还不知道积性函数是什么)，特殊的当$n$为奇数时，$\varphi \left( 2n \right) =\varphi \left( n \right) $。
4.当$n>2$时，$\varphi(n)$必为偶数。
5.比$n$小的所有的数的和为$n\cdot \varphi \left( n \right) /2$。
6.若$a$与$n$互质，则有$a^{\varphi \left( n \right)}\equiv 1\left( \text{mod} n \right) \,\,$，$a^{b\,\,\left( \text{mod} \varphi \left( n \right) \right)}\equiv 1\left( \text{mod} n \right) \,\,$。
例题：
P5091 【模板】扩展欧拉定理
其他没啥就是这个$b$在读入的时候要按照字符读入然后取模，复杂度为$O\left( \sqrt{m}+\log b \right) $，大概就是$1e7$的样子。
TM wa了老半天才知道定理是有使用条件的，最终的定理长这样：
$$a^b=\left\{ \begin{array}{c}
a^b\,\, ,b<\varphi \left( m \right)\\
a^{b\,\,\text{mod} \varphi \left( m \right) +\varphi \left( m \right)}\,\,,b\ge \varphi \left( m \right)\\
\end{array} \right. $$
且此时有$gcd\left( a,m \right) \ne 1$
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=2e5+1000;
ll a,b,mod;
ll euler(ll n){
ll res=n;
for(ll i=2;i*i<=n;i++){
if(n%i==0){
res-=res/i;
while(n%i==0)
n/=i;
}
}
if(n>1) res-=res/n;
return res;
}
inline ll read(ll mod){
ll x=0;char c=getchar();
int yes=0;
while (c<'0'||c>'9') c=getchar();
while (c>='0'&&c<='9'){
x=x*10+c-'0';
if(x>=mod) x=x%mod,yes=1;
c=getchar();
}
if(yes) return x;
else return -x;
}
ll qpow(ll a,ll k){
ll res=1,x=a;
while(k){
if(k&1){
res=x*res%mod;
}
x=x*x%mod;
k>>=1;
}
return res;
}
int main(){
// freopen("in.txt","r",stdin);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
a=-read(1e9+100),mod=-read(1e9+100);
ll phi=euler(mod);
b=read(phi);
if(a%mod==0) cout<<0<<endl;
else{
if(b>=0)
cout<<qpow(a,b+phi)%mod<<endl;
else
cout<<qpow(a,-b)%mod<<endl;
}
return 0;
}
P2158 [SDOI2008]仪仗队
实际上就是求出$1\sim n$内所有互质的点的个数$num$，然后答案就等于$ans=num+2-1$，加$2$是因为$(0,1),(1,0)$未算入，减一是因为$(1,1)$重复计算了。
所以有$ans=2 \sum_{i=0}^{n-1}{\varphi \left( i \right)}+1$。那么就需要快速的求出$\varphi \left( 1 \right) \sim \varphi \left( n \right) $，显然按照之前的求法是不好的，所以这里要用到线性筛法求出，复杂度为$O(n)$废话不然为什么叫线性筛。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=2e5+1000;
ll vis[maxn],p[maxn],phi[maxn];
ll euler(ll n){//朴素单个欧拉函数 O(sqrt(n))
ll res=n;
for(ll i=2;i*i<=n;i++){
if(n%i==0){
res-=res/i;
while(n%i==0)
n/=i;
}
}
if(n>1) res-=res/n;
return res;
}
void neuler(ll n){//得到1~n-1所有的欧拉函数 O(n)
ll cnt=0;
phi[1]=1;
for(int i=2;i<n;i++){
if(!vis[i]){
p[cnt++]=i;
phi[i]=i-1;
}
for(int j=0;j<cnt&&i*p[j]<n;j++){
vis[i*p[j]]=1;
if(i%p[j]==0){
phi[i*p[j]]=phi[i]*p[j];
break;
}
phi[i*p[j]]=phi[i]*(p[j]-1);
}
}
}
int main(){
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll n;
cin>>n;
neuler(n+1);
ll res=0;
if(n==1){
cout<<0<<endl;
return 0;
}
for(int i=0;i<n;i++) res+=phi[i];
cout<<2*res+1<<endl;
return 0;
}
可以看到，其实基本的代码结构是和原本的质数筛相同的。基本上有三点不同，比如第六行的对$\varphi (i)$的赋值和第十一行和十四行的递推。从此也就可以看出线性筛的适用范围。就是当$n$和$m$互质时有：$f\left( n\cdot m \right) =f\left( n \right) \cdot f\left( m \right) $，这也就是积性函数的定义。这个东西太高级了，现在就先当黑箱子用吧，待补(咕咕)。
莫比乌斯函数
定义
$$\mu \left( x \right) =\begin{cases}
\,\, 1 \text{，}x=1\\
-1^k\text{，}x\text{无平方因数且}x=p_1p_2p_3...p_k\\
\,\, 0 \text{，}x\text{有平方因数}\\
\end{cases}$$换句人话就是说如果可以表示为奇数个不同素数的乘积就是-1,如果可以表示为偶数个不同素数的乘积就是1，如果表示出来有相同素数就是0。
单个莫比乌斯函数的朴素算法
1 int mob(ll n){//单个函数的算法 O(sqrt(n))
2 ll cnt=0,temp=0;
3 for(ll i=2;i*i<=n;i++){
4 temp=0;
5 if(n%i==0){
6 while(n%i==0) temp++,n/=i;
7 if(temp>1) return 0;
8 cnt++;
9 }
10 }
11 if(n!=1) cnt++;
12 return (cnt&1)?-1:1;
13 }
相关定理
1.
$$\sum_{d\mid n}{\mu \left( d \right)}=\left\{ \begin{array}{c}
1 \left( n=1 \right)\\
0 \left( n\ne 1 \right)\\
\end{array} \right. $$
当$n=1$时是显然的；当$n \ne 1$时，$d$相当于从$n$的素数乘积表示中选取，故有:
$$\sum_{d\mid n}{\mu \left( d \right)}=\sum_{i=0}^k{\left( -1 \right) ^iC_{k}^{i}}$$
由组合的性质可知后者等于$0$。嗷看了半天才知道，这个定理可以将$n=1$的条件判断变成左边的式子，这样在某些时候就可以化简表达式。
2.
$$\sum_{d\mid n}^{}{\cfrac{\mu \left( d \right)}{d}}=\cfrac{\varphi \left( n \right)}{n}$$
证明略，要用到一些我不会的东西。
线性筛法
显然当$n,m$互质时，由于二者没有共同的因数，所以乘积的表示中不会有同项，由定义可知此时有:
$$\mu \left( n\cdot m \right) =\mu \left( n \right) \cdot \mu \left( m \right) $$
故莫比乌斯函数为积性函数，可以用线性筛法求出。
1 int u[maxn],p[maxn];
2 bool vis[maxn];
3 void nmob(ll n){
4 u[1]=1;
5 ll cnt=0;
6 for(int i=2;i<=n;i++){
7 if(!vis[i])p[++cnt]=i,u[i]=-1;
8 for(int j=1;j<=cnt&&i*p[j]<=n;j++){
9 vis[i*p[j]]=1;
10 if(i%p[j]) u[i*p[j]]=-u[i];
11 else break;
12 }
13 }
14 }
例题
HDOJ-2841
类似于上例中的仪仗队但是对$x,y$的限制不同了，有俩种方法。第一种是利用容斥思想将$y$分解然后对于每个$n$除去相应的因数的个数，但是有的数字会被重复删去，所以要将删去的再次加回来，而这个系数正是该数对应的莫比乌斯函数值；重点看一下第二种方法，利用上面说的等价判断有：
$$\sum_{i=1}^n{\sum_{j=1}^n{\left[ gcd\left( i,j \right) ==1 \right]}}
\\
=\sum_{i=1}^n{\sum_{j=1}^n{\sum_{d\mid gcd\left( i,j \right)}^{}{\mu \left( d \right)}}}
\\
=\sum_{d=1}^{\min \left( n,m \right)}{\mu \left( d \right) \sum_{i=1}^{n/d}{1}\sum_{j=1}^{m/d}{1}}
\\
=\sum_{d=1}^{\min \left( n,m \right)}{\mu \left( d \right) \cdot \frac{n}{d}\cdot \frac{m}{d}}$$
哇，说实话这个变换真的秀，这要我就不可能想得到啊。第一步用的就是定理，但是第二步就很巧妙。因为$d\mid gcd\left( i,j \right) $中要让$d$存在，那么$gcd\left( i,j \right) $必须要大于等$d$所以每一个$d$的贡献就是$$\mu \left( d \right) \sum_{i=1}^{n/d}{1}\sum_{j=1}^{m/d}{1}$$后面之所以是从$1$到$n/d$，就是看$n$最多可以被$d$的几倍整除，然后前面之所以是$\min \left( n,m \right) $是因为$d$最大也只能到这个值且此时$n,m$有倍数关系。然后这个问题就变成了线性问题，结合线性筛就直接就是裸题了，相比于第一种方法代码量要小很多。果然数学越好代码越少。
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const ll maxn=2e5+1000;
5 int mob(ll n){//单个函数的算法 O(sqrt(n))
6 ll cnt=0,temp=0;
7 for(ll i=2;i*i<=n;i++){
8 temp=0;
9 if(n%i==0){
10 while(n%i==0) temp++,n/=i;
11 if(temp>1) return 0;
12 cnt++;
13 }
14 }
15 if(n!=1) cnt++;
16 return (cnt&1)?-1:1;
17 }
18 int u[maxn],p[maxn];
19 bool vis[maxn];
20 void nmob(ll n){
21 u[1]=1;
22 ll cnt=0;
23 for(int i=2;i<=n;i++){
24 if(!vis[i])p[++cnt]=i,u[i]=-1;
25 for(int j=1;j<=cnt&&i*p[j]<=n;j++){
26 vis[i*p[j]]=1;
27 if(i%p[j]) u[i*p[j]]=-u[i];
28 else break;
29 }
30 }
31 }
32 ll t,n,m;
33 int main(){
34 //freopen("in.txt","r",stdin);
35 ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
36 cin>>t;
37 nmob(1e5+100);
38 while(t--){
39 cin>>n>>m;
40 ll xiao=min(n,m),res=0;
41 for(int d=1;d<=xiao;d++){
42 ll a=n/d,b=m/d;
43 res+=a*b*u[d];
44 }
45 cout<<res<<endl;
46 }
47 return 0;
48 }