狄利克雷卷积总结

积性函数

常见的积性函数： φ , μ , σ , d \large \varphi,\mu,\sigma,d φ,μ,σ,d

常见的完全积性函数： ϵ , I , i d \large \epsilon,I,id ϵ,I,id

函数名	数学表达式
欧拉函数	φ ( n ) \varphi(n) φ(n)
莫比乌斯函数	μ ( n ) \mu(n) μ(n)
元函数	ϵ ( n ) = [ n = 1 ] \epsilon(n)=[n=1] ϵ(n)=[n=1]
恒等函数	I ( n ) = 1 I(n)=1 I(n)=1
约数个数函数	d ( n ) d(n) d(n)
约数和函数	σ ( n ) \sigma(n) σ(n)
一次函数	i d ( n ) = n id(n)=n id(n)=n

---

狄利克雷卷积

狄利克雷卷积的性质

证明性质3

恒等函数在狄利克雷卷积中是相当于单位元的存在

f ∗ ϵ = f \large f* \epsilon =f f∗ϵ=f

证明：

= ∑ d ∣ n f ( d ) ϵ ( n d ) \large =\sum\limits_{d|n}f(d)\epsilon(\dfrac{n}{d}) =d∣n∑​f(d)ϵ(dn​)

当且仅当 d = n d=n d=n时， f ( d ) ϵ ( n d ) = f ( n ) ≠ 0 f(d)\epsilon(\dfrac{n}{d})=f(n)\ne 0 f(d)ϵ(dn​)=f(n)​=0

则 f ∗ ϵ = f \large f * \epsilon = f f∗ϵ=f

莫比乌斯反演的证明

若 g ( n ) = ∑ d ∣ n f ( d ) g(n)=\sum\limits_{d|n}f(d) g(n)=d∣n∑​f(d)

则 f ( n ) = ∑ d ∣ n μ ( d ) g ( n d ) f(n)=\sum\limits_{d|n}\mu(d)g(\dfrac{n}{d}) f(n)=d∣n∑​μ(d)g(dn​)

证明:

利用 D i r i c h l e t Dirichlet Dirichlet卷积的性质即可： μ ∗ I = ϵ \mu * I =\epsilon μ∗I=ϵ

给出的条件等价于

g = f ∗ I \large g=f* I g=f∗I

g ∗ μ = f ∗ μ ∗ I = f ∗ ϵ = f \large g*\mu= f * \mu * I =f * \epsilon=f g∗μ=f∗μ∗I=f∗ϵ=f

---

杜教筛

杜教筛可用来在非线性时间求解积性函数的前缀和

引用一波，但是第一行没写好。

= ∑ i = 1 n ∑ d ∣ i f ( d ) g ( i d ) = ∑ i = 1 n ∑ d ∣ i f ( i d ) g ( d ) \large=\sum\limits_{i=1}^n\sum\limits_{d|i} f(d)g(\dfrac{i}{d})=\sum\limits_{i=1}^n\sum\limits_{d|i} f(\dfrac{i}{d})g(d) =i=1∑n​d∣i∑​f(d)g(di​)=i=1∑n​d∣i∑​f(di​)g(d)

这样比较好理解。

---

几个简单的应用

1. μ \mu μ的前缀和

S ( n ) = ∑ i = 1 n ( f ∗ g ) ( i ) − ∑ i = 2 n g ( i ) S ( n i ) \large S(n)=\sum\limits_{i=1}^n(f*g)(i)-\sum\limits_{i=2}^ng(i)S(\dfrac{n}{i}) S(n)=i=1∑n​(f∗g)(i)−i=2∑n​g(i)S(in​)

f = μ , g = I , f ∗ g = ϵ f=\mu, g=I,f*g=\epsilon f=μ,g=I,f∗g=ϵ

∑ i = 1 n ϵ ( i ) = 1 \sum\limits_{i=1}^n\epsilon(i)=1 i=1∑n​ϵ(i)=1

∑ i = 2 n g ( i ) S ( n i ) \sum\limits_{i=2}^ng(i)S(\dfrac{n}{i}) i=2∑n​g(i)S(in​) 这一部分用整除分块+递归解决。

∑ i = l r I ( i ) = r − l + 1 \sum\limits_{i=l}^r I(i)=r-l+1 i=l∑r​I(i)=r−l+1

采用预处理+记忆化 节省时间。

核心代码：

unordered_map<int,int>smu;
int get_mu(int n){
	if(n<N) return mu[n];//线性筛预处理一部分(5e6)
	if(smu[n]) return smu[n];//记忆化
	ll s=1;//左部分
	for(ll l=2,r;l<=n;l=r+1){ //整除分块.
		r=n/(n/l);
		s-=(r-l+1)*get_mu(n/l);
	}
	return smu[n]=s;
}

2. φ \varphi φ的前缀和

考虑 φ ∗ I = i d \varphi * I =id φ∗I=id

左部分即为： ∑ i = 1 n i d ( i ) = n ( n + 1 ) 2 \sum\limits_{i=1}^n id(i)=\dfrac{n(n+1)}{2} i=1∑n​id(i)=2n(n+1)​

ll get_phi(int n){
	if(n<N) return phi[n];//线性筛预处理一部分(5e6)
	if(sphi[n]) return sphi[n];//记忆化
	ll s=1LL*n*(1LL*n+1)>>1;//左部分
	for(ll l=2,r;l<=n;l=r+1){//整除分块.
		r=n/(n/l);
		s-=1LL*(r-l+1)*get_phi(n/l);
	}
	return sphi[n]=s;	//记忆化
}

3.$\varphi $ 结合 i i i

求 ∑ i = 1 n φ ( i ) ⋅ i \sum\limits_{i=1}^n \varphi(i)\cdot i i=1∑n​φ(i)⋅i

这里下面是点乘 ⋅ \huge \cdot ⋅，不是卷积 ∗ * ∗

令 f = φ ⋅ i d , g = i d f=\varphi \cdot id,g=id f=φ⋅id,g=id

( f ∗ g ) ( n ) \large (f*g)(n) (f∗g)(n)

= ∑ d ∣ n φ ( d ) ⋅ d ⋅ n d = n ∑ d ∣ n φ ( d ) = n 2 \large =\sum\limits_{d|n} \varphi(d)\cdot d\cdot \dfrac{n}{d}=n\sum\limits_{d|n}\varphi(d)=n^2 =d∣n∑​φ(d)⋅d⋅dn​=nd∣n∑​φ(d)=n2

所以左部分的前缀和可以 O ( 1 ) O(1) O(1)求出。

∑ ( f ∗ g ) ( i ) = ∑ 1 n i 2 = n ( n + 1 ) ( 2 n + 1 ) 6 \large \sum\limits (f*g)(i)=\sum\limits_{1}^n i^2=\dfrac{n(n+1)(2n+1)}{6} ∑(f∗g)(i)=1∑n​i2=6n(n+1)(2n+1)​

4. φ \varphi φ的综合

∑ i = 1 n ∑ j = 1 n i j ∑ d ∣ i , d ∣ j φ ( d ) \sum\limits_{i=1}^n \sum\limits_{j=1}^n ij \sum\limits_{d|i,d|j}\varphi(d) i=1∑n​j=1∑n​ijd∣i,d∣j∑​φ(d)

= ∑ d = 1 n φ ( d ) ∑ d ∣ i ∑ d ∣ j i j =\sum\limits_{d=1}^n\varphi(d)\sum\limits_{d|i}\sum\limits_{d|j} ij =d=1∑n​φ(d)d∣i∑​d∣j∑​ij

= ∑ d = 1 n φ ( d ) d 2 ( ∑ i = 1 n d i ) 2 =\sum\limits_{d=1}^n \varphi(d)d^2 (\sum\limits_{i=1}^{\dfrac{n}{d}}i)^2 =d=1∑n​φ(d)d2(i=1∑dn​​i)2

= ∑ d = 1 n φ ( d ) d 2 ∑ i = 1 n d i 3 =\sum\limits_{d=1}^n\varphi(d)d^2\sum\limits_{i=1}^{\dfrac{n}{d}}i^3 =d=1∑n​φ(d)d2i=1∑dn​​i3

倒数第二步转到最后一步是因为： ∑ i = 1 n i = n ( n + 1 ) 2 \sum\limits_{i=1}^n i=\dfrac{n(n+1)}{2} i=1∑n​i=2n(n+1)​

∑ i = 1 n i 3 = ( n ( n + 1 ) 2 ) 2 \sum\limits_{i=1}^n i^3 =(\dfrac{n(n+1)}{2})^2 i=1∑n​i3=(2n(n+1)​)2

所以可以消掉一个求和。

原柿子可化简为： ∑ d = 1 n φ ( d ) d 2 ∑ i = 1 n d i 3 \large \sum\limits_{d=1}^n \varphi(d)d^2 \sum\limits_{i=1}^{\dfrac{n}{d}}i^3 d=1∑n​φ(d)d2i=1∑dn​​i3

考虑整除分块求。

右边的前缀和可 O ( 1 ) O(1) O(1)求，左边记位：$f(n)=\large \sum\limits_{i=1}^n \varphi(i)i^2 $

考虑杜教筛，求 f ( n ) f(n) f(n)

f = ∑ φ ⋅ i d 2 f=\sum \varphi \cdot id^2 f=∑φ⋅id2

考虑用 g = i d 2 g=id^2 g=id2

则 f ∗ g = n 2 ∑ d ∣ n φ ( d ) = n 3 f*g=n^2\sum\limits_{d|n}\varphi(d)=n^3 f∗g=n2d∣n∑​φ(d)=n3

因此 f ( n ) = ∑ i = 1 n i 3 − ∑ i = 2 n g ( i ) f ( n i ) f(n)=\sum\limits_{i=1}^n i^3-\sum\limits_{i=2}^n g(i)f(\dfrac{n}{i}) f(n)=i=1∑n​i3−i=2∑n​g(i)f(in​)

左边的前缀和 O ( 1 ) O(1) O(1)求。

∑ i = 1 n i 3 = ( n ( n + 1 ) 2 ) 2 \sum\limits_{i=1}^n i^3=(\dfrac{n(n+1)}{2})^2 i=1∑n​i3=(2n(n+1)​)2

上面整除分块即可。

总结：推式子，杜教筛+两次整除分块。

code

// Problem: P3768 简单的数学题
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3768
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// Date: 2021-07-07 16:19:04
// --------by Herio--------

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int N=5e6+5,M=2e4+5,inf=0x3f3f3f3f;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(false),cin.tie(0) 
void Print(int *a,int n){
	for(int i=1;i<n;i++)
		printf("%d ",a[i]);
	printf("%d\n",a[n]); 
}
int mod;
ll ksm(ll a,ll n,ll mod=mod){
	ll s=1;
	while(n){
		if(n&1) s=s*a%mod;
		a=a*a%mod;
		n>>=1;
	}
	return s;
}
ll inv6;
ll f2(ll n){
	n%=mod;
	return (n*(n+1)%mod)*((2*n%mod+1)%mod)%mod*inv6%mod;
}
ll f3(ll n){
	n%=mod;
	return (n*(n+1)/2%mod)*(n*(n+1)/2%mod)%mod;
}
bitset<N>vis;
int p[N],cnt;
int phi[N];
int sphi[N];
void init(int n){
	vis[1]=phi[1]=1;
	for(int i=2;i<=n;i++){
		if(!vis[i]) p[++cnt]=i,phi[i]=i-1;
		for(int j=1;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]*phi[p[j]];
		}
	}
	for(int i=1;i<=n;i++) sphi[i]=(sphi[i-1]+1LL*i*i%mod*phi[i]%mod)%mod;
}
unordered_map<ll,int>mp;
#define ck(s) s<0?s+mod:s;
int fun(ll n){
	if(n<N) return sphi[n];
	if(mp[n]) return mp[n];
	ll s=f3(n);
	for(ll l=2,r;l<=n;l=r+1){
		r=n/(n/l);
		s=s-(f2(r)-f2(l-1)+mod)*fun(n/l)%mod;
		s=ck(s);
	}
	return mp[n]=s;
}
int solve(ll n){
	ll s=0;
	for(ll l=1,r;l<=n;l=r+1){
		r=n/(n/l);
		s=(s+f3(n/l)*(fun(r)-fun(l-1)+mod)%mod)%mod;
	}
	return s;
}
int main(){
	ll n;
	scanf("%d%lld",&mod,&n);
	init(N-1);
	inv6=ksm(6,mod-2);
	printf("%d\n",solve(n));
	return 0;
}