题解 P3768 【简单的数学题】

· · 题解

--- 首先要知道：（欧拉反演） $$\varphi*1=\mathrm{id}$$ 即 $$\sum\limits_{d\mid n}\varphi(d)=n$$ 这道题就是让求： $$\sum\limits_{i=1}^n{\sum\limits_{j=1}^{n}{ij\cdot \mathrm{id}\left(\gcd(i,j)\right)}}$$ 带入最开头说的那个式子得到： (由于 $d$ 能被 $\gcd(i,j)$ 整除，所以 $d$ 既能被 $i$ 整除也能被 $j$ 整除，$d$ 的取值范围就珂以写成：$d\mid i,d\mid j$ ） $$\sum\limits_{i=1}^n{\sum\limits_{j=1}^{n}{ij\sum\limits_{d\mid i,d\mid j}\varphi(d)}}$$ 套路的，我们把 $d$ 搞出来枚举： $$\sum\limits_{d=1}^{n}{\varphi(d)}\sum\limits_{d\mid i}\sum\limits_{d\mid j}ij$$ 由于 $i,j$ 都是 $d$ 的倍数，所以我们珂以把它们都除以 $d$,别忘了把 $d$ 再乘回去！ $$\sum\limits_{d=1}^{n}{\varphi(d)\cdot d^2}\sum\limits_{i=1 }^{\left\lfloor\frac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}ij$$ 发现 $i,j$ 的取值范围是一样的，所以直接把它们合并掉！ $$\sum\limits_{d=1}^{n}{\varphi(d)\cdot d^2}\left(\sum\limits_{i=1 }^{\left\lfloor\frac{n}{d}\right\rfloor}i\right)^2$$ 后面的那个求和就珂以数论分块啦！ 求的话珂以 $\mathcal{O}(1)$ 搞掉 (相信只要上过小学的人都会）： $$\left(\sum\limits_{i=1}^{n}i\right)^2=\frac{n^2(n+1)^2}{4}$$ 前面的 $\sum\limits_{d=1}^{n}{\varphi(d)\cdot d^2}$ 怎么办？ [**杜教筛**！！](https://www.luogu.com.cn/problem/P4213) 令 $f=\varphi \cdot \mathrm{id}^2$,需要再找一个合适的 $g

为了让 (f*g)(n) 求前缀和方便，我们最好不让式子里有除 n 以外的变量。

由于 d\cdot \frac{n}{d}=n （废话。。）

我们就让 g=\mathrm{id}^2 来消掉 d

那么:

&=n^2\sum\limits_{d\mid n}\varphi(d) \\ &=n^3 \end{aligned}

(最后一步依然用到了：\varphi*1=\mathrm{id} )

令 S(n)=\sum\limits_{d=1}^{n}{\varphi(d)\cdot d^2}

直接套杜教筛的公式即可：

S(n)=\frac{\sum\limits_{i=1}^{n}(f*g)(n)-\sum\limits_{i=2}^{n}{g(i)S}\left(\left\lfloor\frac{n}{i}\right\rfloor\right)}{g(1)}

求 (f*g)(n) 和 g(n) 的前缀和还是小学生难度：

\sum\limits_{i=1}^{n}(f*g)(i)=\sum\limits_{i=1}^{n}i^3=\frac{n^2(n+1)^2}{4} \sum_{i=1}^{n}g(i)=\sum\limits_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}

先筛出来大约 n^{\frac{2}{3}} 个 S(i)，这样 S(n) 就可以在 \mathcal{O}(n^{\frac{2}{3}}) 的时间复杂度内求出来。

虽然外面再套一个数论分块，但复杂度还是 \mathcal{O}(n^{\frac{2}{3}})（不过如果套两层数论分块就不一定了）。

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
#define N 5000050
typedef long long ll;
const int MAX=5000000;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*f;
}
#define ck(x) (x>=mod?x-mod:x)
map<ll,ll> mp;
ll mod,n,Sphi[N],inv6;
int phi[N],primes[N>>2],pn;
bool ntp[N];
ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
void init(int n){//预处理S(i)
    ntp[1]=true,phi[1]=1;
    for(register int i=2;i<=n;++i){
        if(!ntp[i])primes[++pn]=i,phi[i]=i-1;
        for(int j=1;j<=pn&&primes[j]*i<=n;++j){
            ntp[primes[j]*i]=true;
            if(i%primes[j]==0){
                phi[i*primes[j]]=phi[i]*primes[j];
                break; 
            }
            phi[i*primes[j]]=phi[i]*(primes[j]-1);
        }
    }
    for(register int i=1;i<=n;i++){
        Sphi[i]=Sphi[i-1]+1LL*i*i%mod*phi[i]%mod;
        Sphi[i]=ck(Sphi[i]);
    }
}
inline ll S2(ll n){//平方和
    n%=mod;
    return n*(n+1)%mod*(2*n+1)%mod*inv6%mod;
}
inline ll S3(ll n){//立方和
    n%=mod;
    return (n*(n+1)/2%mod)*(n*(n+1)/2%mod)%mod;
}
inline ll Get(ll n){//杜教筛求S(n)
    if(n<=MAX)return Sphi[n]%mod;
    if(mp.count(n))return mp[n];
    ll r=0,ans=S3(n);
    for(ll l=2;l<=n;l=r+1){
        r=(n/(n/l));
        ans-=(S2(r)-S2(l-1)+mod)%mod*Get(n/l)%mod;
        ans=ck(ans+mod);
    } 
    return mp[n]=ans;
}
ll Solve(ll n){
    ll r=0,ans=0;
    for(ll l=1;l<=n;l=r+1){//先在外层数论分块一下
        r=(n/(n/l));
        ans+=S3(n/l)*(Get(r)-Get(l-1)+mod)%mod;
        ans=ck(ans);
    }
    return ans;
}
int main(){
    mod=read(),n=read();
    init(MAX),inv6=qpow(6,mod-2);
    printf("%lld\n",Solve(n));
    return 呱呱！
}

Froggy's blog

呱!!