写个所有常见的积性函数的欧拉筛法求法
first 莫比乌斯函数
只是存个板子呜
st[1]=true,mu[1]=1;
rep(i,2,N-1)
{
if(!st[i]) primes[cnt++]=i,mu[i]=-1;//莫比乌斯写出锅了哈哈
for(int j=0;primes[j]*i<N;j++)
{
st[i*primes[j]]=true;
if(i%primes[j]) mu[i*primes[j]]=mu[i]*mu[primes[j]];
else
{
mu[i*primes[j]]=0;break;
}
}
}
second 乘法逆元
积性函数求法
inv[1]=1;
rep(i,2,n) inv[i]=(-(mod/i)*inv[mod%i]%mod+mod)%mod;
递推求法
fac[0]=inv[0]=1;
rep(i,1,n) fac[i]=fac[i-1]*i%mod;
inv[n]=qmi(fac[n],mod-2,mod);
rep(i,1,n-1) inv[i]=inv[i+1]*(i+1)%mod;
third 欧拉函数
st[1]=true,phi[1]=1;
rep(i,2,N-1)
{
if(!st[i]) primes[cnt++]=i,phi[i]=i-1;
for(int j=0;primes[j]*i<N;j++)
{
st[i*primes[j]]=true;
if(i%primes[j]) mu[i*primes[j]]=phi[i]*phi[primes[j]];
else
{
phi[i*primes[j]]=phi[i]*primes[j];break;
}
}
}
fourth约数个数
不是很难啦
st[1]=true,d[1]=1;
rep(i,2,N-1)
{
if(!st[i]) primes[cnt++]=i,d[i]=2,pred[i]=1;//pred[i]表示i的最小质因子的指数
for(int j=0;primes[j]*i<N;j++)
{
st[i*primes[j]]=true;
if(i%primes[j]) d[i*primes[j]]=d[i]*d[primes[j]],pred[i*primes[j]]=1;
else
{
pred[i*primes[j]]=pred[i]+1,d[i*primes[j]]=d[i]/(pred[i]+1)*(pred[i]+2);
break;
}
}
}
fifth约数和
st[1]=true,d[1]=1,f[1]=1;
rep(i,2,N-1)
{
if(!st[i]) primes[cnt++]=i,sumd[i]=i+1,powd[i]=i,f[i]=i+1;
//sumd[i]表示i最小质因子p的形如1+p+p^2+..的形式
//powd[i]表示i最小质因子的最大形式p^maxn
//f[i]是i的约数和
for(int j=0;primes[j]*i<N;j++)
{
st[i*primes[j]]=true;
if(i%primes[j])
{
sumd[i*primes[j]]=1+primes[j],powd[i*primes[j]]=primes[j];
f[i*primes[j]]=f[i]*f[primes[j]];
}
else
{
powd[i*primes[j]]=powd[i]*primes[j];
sumd[i*primes[j]]=sumd[i]+powd[i*primes[j]];
f[i*primes[j]]=f[i]/sumd[i]*sumd[i*primes[j]];
break;
}
}
}
积性函数还可以优化一些题目的时间
华华给月月出题
原来的暴力TLE代码
TLE的锅在快速幂那里需要多乘logn的时间复杂度
#include<bits/stdc++.h>
using namespace std;
#define read(x) scanf("%lld",&x)
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define int long long
const int mod=1e9+7;
int qmi(int a, int k, int p) // 求a^k mod p
{
int res = 1 % p;
while (k)
{
if (k & 1) res = res * a % p;
a = a * a % p;
k >>= 1;
}
return res;
}
signed main()
{
int n;read(n);
int ans=0;
rep(i,1,n)
{
ans^=qmi(i,n,mod);
}
cout<<ans<<endl;
}
用积性函数就只需要质数快速幂就好了
算了一下大概是3e7的时间复杂度
#include<bits/stdc++.h>
using namespace std;
#define read(x) scanf("%lld",&x)
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define int long long
const int mod=1e9+7;
const int N=13e6+5;
bool st[N];
int primes[N],fac[N],cnt,n;
int qmi(int a, int k, int p) // 求a^k mod p
{
int res = 1 % p;
while (k)
{
if (k & 1) res = res * a % p;
a = a * a % p;
k >>= 1;
}
return res;
}
void init()
{
st[1]=true,fac[1]=1;
rep(i,2,N-1)
{
if(!st[i]) primes[cnt++]=i,fac[i]=qmi(i,n,mod);
for(int j=0;primes[j]*i<N;j++)
{
st[i*primes[j]]=true;
fac[i*primes[j]]=fac[i]*fac[primes[j]]%mod;
if(i%primes[j]==0) break;
}
}
}
signed main()
{
read(n);
int ans=0;
init();
rep(i,1,n)
{
ans^=fac[i];
}
cout<<ans<<endl;
}
莫比乌斯反演
还是不太会构造呜呜
序列
存个经典例子
多少个有序对 < x,y > 满足gcd(x,y)=1,超级经典
看图
这样一来问题就转化为怎么求f[i]
那就枚举叭
#include<bits/stdc++.h>
using namespace std;
#define read(x) scanf("%lld",&x)
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define rrep(i,x,y,z) for(int i=x;i<=y;i+=z)
#define int long long
const int mod=1e9+7;
const int N=1e5+10;
bool st[N];
int cnt,primes[N],mu[N],res[N],n,f[N];
int a[N],b[N];
void init()
{
st[1]=true,mu[1]=1;
rep(i,2,N-1)
{
if(!st[i]) primes[cnt++]=i,mu[i]=-1;
for(int j=0;primes[j]*i<N;j++)
{
st[i*primes[j]]=true;
if(i%primes[j]) mu[i*primes[j]]=mu[i]*mu[primes[j]];
else
{
mu[i*primes[j]]=0;break;
}
}
}
}
signed main()
{
init();
read(n);
rep(i,1,n) read(a[i]);
rep(i,1,n) read(b[i]);
rep(i,1,n)
{
rrep(j,i,n,i) res[a[b[j]]]++;
rrep(j,i,n,i) f[i]+=res[b[a[j]]];
rrep(j,i,n,i) res[a[b[j]]]=0;
}
int ans=0;
rep(i,1,n)
ans+=mu[i]*f[i];
cout<<ans<<endl;
return 0;
}
好