HYSBZ4916(杜教筛)

题目链接

神犇和蒟蒻

题解

很显然，第一个求$\sum_{i=1}^n\mu(i)$的结果肯定是1
那么我们来看第二个问题就

$$\begin{aligned} Ans&=\sum_{i=1}^n\phi(i^2)\\ &=\sum_{i=1}^ni\phi(i)\\ \end{aligned}$$

设

$$f(n)=i*\phi(i)$$

那么它与Id(n)=n的迪利克雷卷积就是

$$f*id=\sum_{d|n}\phi(d)d*\frac{n}{d}=\sum_{d|n}\phi(d)*n$$ $$\begin{aligned} \sum_{i=1}^nf*id&=\sum_{i=1}^n\sum_{d|i}\phi(d)*i\\ &=\sum_{i=1}^ni\sum_{d|n}\phi(d) &=\sum_{i=1}^ni^2 \end{aligned}$$

这样我们就能轻松求得f*id的前缀和，也可以得到id的前缀和，然后就套用杜教筛的模板就好了。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N = 2e6+10;
bool vis[N];
ll prime[N],cnt,mu[N],phi[N];
bool visphi[N];
ll sumphi[N],n;
const int mod = 1e9+7;
ll get_sumphi(ll n){
	return n<N?phi[n]:sumphi[N/n];
}
void init(){
	phi[1]=1;
	mu[1]=1;
	for(int i=2;i<N;i++){
		if(!vis[i])prime[cnt++]=i,phi[i]=i-1,mu[i]=-1;
		for(int j=0;j<cnt&&i*prime[j]<N;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j]==0){
				phi[i*prime[j]]=phi[i]*prime[j];
				mu[i*prime[j]]=0;
				break;
			}
			mu[i*prime[j]]=-mu[i];
			phi[i*prime[j]]=phi[i]*(prime[j]-1);

		}
	}
	for(int i=1;i<N;i++){
	phi[i]=(1ll*phi[i]*i)%mod;
	phi[i]=(phi[i]+phi[i-1])%mod; 
	}
}

ll getSum3(int n){
	ll a = n,b=n+1,c=2*n+1;
	if(a%2==0)a/=2;
	else if(b%2==0)b/=2;
	else if(c%2==0)c/=2;
	if(a%3==0)a/=3;
	else if(b%3==0)b/=3;
	else if(c%3==0)c/=3;
	return 1ll*(a*b%mod)*c%mod;
}
ll getSum2(int n){
	ll a =n,b=n+1;
	if(a%2==0)a/=2;
	else b/=2;
	return a*b%mod;
}
ll getSumphi(int x){
	if(x<N)return phi[x];
	if(visphi[n/x])return sumphi[n/x];
	ll res = getSum3(x);
	for(ll l=2,r;l<=x;l=r+1){
		r=x/(x/l);
		res=(res-1ll*(getSum2(r)-getSum2(l-1))*getSumphi(x/l)+mod)%mod;
	}visphi[n/x]=1,sumphi[n/x]=res;
	return res;
}
int main(){
	init();
	scanf("%lld",&n);
	memset(visphi,0,sizeof(visphi));
	printf("1\n%lld\n",getSumphi(n));
	return 0;
}