求和(莫比乌斯反演+杜教筛)

题目链接

思路

$\begin{aligned} f(n)&=\sum_{i=1}^{n}\sum_{j=1}^{n}gcd(i,j,n)\\ &=\sum_{d|n}d\sum_{i=1}^{n}\sum_{j=1}^{n}[gcd(i,j,n)==1]\\ &=\sum_{d|n}d\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}[gcd(i,j,\frac{n}{d})==1]\\ &=\sum_{d|n}d\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}\sum_{k|gcd(i,j,\frac{n}{d})}\mu(k)\\ &=\sum_{d|n}d\sum_{k|\frac{n}{d}}\mu(k)(\frac{n}{dk})^2\\ 令T=dk\\ &=\sum_{T|n}(\frac{n}{T})^2\sum_{k|T}\mu(\frac{T}{k})k\\ &=\sum_{T|n}(\frac{n}{T})^2\phi(T)\\ &=\sum_{T|n}T^2\phi(\frac{n}{T}) \end{aligned}$

那么可以得到

$\begin{aligned} F(n)&=\sum_{i=1}^{n}f(n)=\sum_{i=1}^n\sum_{T|i}T^2\phi(\frac{i}{T})\\ &=\sum_{i=1}^{n}T^2\sum_{k=1}^{\lfloor\frac{n}{i}\rfloor}\phi(k) \end{aligned}$

然后我们只要处理出$\phi$函数的前缀和就可以分块求解这个问题了

杜教筛

为了求出$\phi$函数的前缀和，我们采用杜教筛的方法

狄利克雷卷积

先来了解什么是迪利克雷卷积，首先
$f,g$是两个数论函数，那么他们的卷积就是

$(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})$

性质1

满足交换律结合律等，且单位元为$\epsilon$
那么可以得到以下几个性质

$\mu * I = \epsilon$ $\phi* I = id$ $\mu * id = \phi$

解释以下上述符号的意义

$\mu$表示莫比乌斯函数
$I表示全1函数，即I(n)=1$
$id：id(n)=n$

杜教筛的目的是为了求

$S(n)=\sum_{i=1}^nf(i)$

假设有一个积性函数g，考虑f和g的迪利克雷卷积

$\begin{aligned} \sum_{i=1}^nf*g(n)&=\sum_{i=1}^n\sum_{d|i}g(d)f(\frac{i}{d})\\ &=\sum_{i=1}^ng(d)\sum_{k=1}^{\lfloor\frac{n}{i}\rfloor}f(k) &=\sum_{i=1}^ng(i)S(\lfloor\frac{n}{i}\rfloor) \end{aligned}$

然后我们考虑如何从这个式子中得到$S(n)$ 考虑下面这个式子

$\sum_{i=1}^ng(i)S(\lfloor\frac{n}{i}\rfloor)-\sum_{i=2}^ng(i)S(\lfloor\frac{n}{i}\rfloor)=S(n)g(1)$

我们只要找到一个函数g，使得 $(g×f)(n)$ 的前缀和可以被迅速求得,就可以利用上面的这个公式进行分块来求的原来的S(n)了，当然，g函数的话也要能够轻易求得前缀和。一般的选取为刚刚上述解释的几个函数，$\epsilon\quad I\quad id$ 等。
现在我们需要求的是 $\phi$ 函数的前缀和，我们假设$f=\phi$根据上面的性质，我们知道
$\phi*I=id$ 那么，I是全一函数，id是等差数列我们都可以O(1)求得他们的前缀和，这样我们就能够轻易的求得$\phi$的前缀和了。
代码如下

ll getSumu(int n){
      if(n<maxn)return sum[n];//此处是先筛出一部分的前缀和，作为递归出口
      if(sumu[n])return sumu[n];//利用map来进行记忆化搜索，能够提速
      ll res = 1ll*n*(n+1)/2;这里就是g函数的前缀和
      for(int i=2,last;i<=n;i=last+1){
            last = n/(n/i);
            res-=(last-i+1)*getSumu(n/l);//减去的后面的部分,递归求解
      }
      return sumu[n]=res;//得到答案
}

代码示例

好了，我们已经做出了这道题，通过杜教筛求出$\phi$函数的前缀和，然后通过分块求出F(n)。


#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int maxn = 1e5+10;
bool vis[maxn];
int prime[maxn],cnt;
int sum[maxn];
map<ll,ll>Sumu;
int phi[maxn];
int n,mod;
const int md= 1e9+7;
void init()
{
    phi[1]=1;
    for(int i=2;i<maxn;i++){
    	if(!vis[i])prime[cnt++]=i,phi[i]=i-1;
    	for(int j=0;j<cnt&&i*prime[j]<maxn;j++){
    		vis[i*prime[j]]=1;
    		if(i%prime[j]==0){
    			phi[i*prime[j]]=phi[i]*prime[j];
    			break;
			}
			phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}
	for(int i=1;i<maxn;i++)sum[i]=(sum[i-1]+phi[i])%mod;
}
ll getSumu(int n){
	if(n<maxn)return sum[n];
	if(Sumu[n])return Sumu[n];
	ll ret = 1ll*n*(n+1)/2;
	for(int l=2,r;l<=n;l=r+1){
		r=n/(n/l);
		ret=(ret-(r-l+1)*getSumu(n/l)+mod)%mod;
	}
	return Sumu[n]=ret;
} 
ll getsum(__int128 n){
    __int128 x=n*(n+1)*(n*2+1)/6;
    return x%mod;
}
int main(){
	
	scanf("%d %d",&n,&mod);
	init();
	ll ans = 0;
	for(int i=1,last;i<=n;i=last+1){
		last=n/(n/i);
		ll a = getsum(last)-getsum(i-1);
		ll b = getSumu(n/i);
		ans=(ans+a*b+mod)%mod;
	}
	printf("%lld\n",ans); 
}