简单的数学题解题报告

解题报告

---

简单的数学题解题报告：

题意：求$(\sum_{i=1}^N\sum_{j=1}^n ij\gcd(i,j))\bmod p$

数据范围：$n\leqslant 10^{10}$且$5\cdot10^8\leqslant p\leqslant 1.1\cdot10^9$，保证$p$为质数

做这道题前，请保证你已经学会莫比乌斯反演和杜教筛0，否则可以到我博珂里康康：
狄利克雷卷积&莫比乌斯反演学习笔记
杜教筛学习笔记

开始推式子：

$$\sum_{i=1}^n\sum_{j=1}^n i\cdot j\cdot\gcd(i,j)=\sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}[\gcd(i,j)==1](i\cdot d)\cdot(j\cdot d)\cdot d\\=\sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}i\cdot j\cdot d^3\cdot(\sum_{k\mid\gcd(i,j)}\mu(k))=\sum_{d=1}^n d^3\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\sum_{i=1}^{\lfloor\frac{n}{d\cdot k}\rfloor}(i\cdot k)\sum_{j=1}^{\lfloor\frac{n}{d\cdot k}\rfloor}(j\cdot k)\\=\sum_{d=1}^n d^3\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\cdot k^2\sum_{i=1}^{\lfloor\frac{n}{d\cdot k}\rfloor}i\sum_{j=1}^{\lfloor\frac{n}{d\cdot k}\rfloor}j$$
设$sum(i)=\frac{i\cdot(i+1)}{2}$，即$1$加到$i$的和
因此： $$\sum_{i=1}^n\sum_{j=1}^n i\cdot j\cdot\gcd(i,j)=\sum_{d=1}^n\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}d^3\cdot\mu(k)\cdot k^2\cdot sum(\lfloor\frac{n}{d\cdot k}\rfloor)^2\\=\sum_{t=1}^n t^2\cdot sum(\lfloor\frac{n}{t}\rfloor)^2\cdot\sum_{d\mid t} d\cdot\mu(\frac{t}{d})$$
用狄利克雷卷积推一下： $$\varphi\cdot I=id\Rightarrow\varphi\cdot I\cdot\mu=id\cdot\mu\Rightarrow id\cdot\mu=\varphi$$
因此继续化简：
$$\sum_{i=1}^n\sum_{j=1}^n i\cdot j\cdot\gcd(i,j)=\sum_{t=1}^n t^2\cdot sum(\lfloor\frac{n}{t}\rfloor)\cdot\varphi(t)$$
设$f(n)=n^2\cdot\varphi(n)$
我们很容易看出$f$是积性函数，因为：
由于$\varphi$为积性函数，若$\gcd(n,m)=1$，则$f(n)$与$f(m)$相乘得：
$$f(n)\cdot f(m)=n^2\cdot\varphi(n)\cdot m^2\cdot\varphi(m)=(n\cdot m)^2\cdot\varphi(n\cdot m)=f(n\cdot m)$$
因此我们可以用杜教筛来处理$f$的前缀和，原式化为：$\sum_{i=1}^n sum(\lfloor\frac{n}{t}\rfloor)\cdot f(t)$，此时原式可以数论分块来做
考虑如何筛$f$，我们设另一个数论函数为$g$，则它们的卷积为：$(f\cdot g)(x)=\sum_{d\mid x}f(d)\cdot g(\frac{x}{d})=\sum_{d\mid x}d^2\cdot\varphi(d)\cdot g(\frac{x}{d})$
我们尝试用$g$消去$d^2$这个项，设$g(x)=x^2$，然后可以推出来： $$(f\cdot g)(x)=\sum_{d\mid x} d^2\cdot\varphi(d)\cdot(\frac{x}{d})^2=\sum_{d\mid x}x^2\cdot\varphi(d)=x^2\cdot\sum_{d\mid x}\varphi(d)$$
由欧拉反演$\sum_{d\mid n}\varphi(d)=n$得： $$(f\cdot g)(x)=x^3$$
因此可以用杜教筛的式子，设$S$为$f$的前缀和： $$g(1)\cdot S(n)=\sum_{i=1}^n(f\cdot g)(i)-\sum_{i=2}^n g(i)\cdot S(\lfloor\frac{n}{i}\rfloor)\\\Rightarrow 1^2\cdot S(n)=\sum_{i=1}^n i^3-\sum_{i=2}^n g(i)\cdot S(\lfloor\frac{n}{i}\rfloor)\\\Rightarrow S(n)=\sum_{i=1}^n i^3-\sum_{i=2}^n i^2\cdot S(\lfloor\frac{n}{i}\rfloor)$$
我们可以用小学奥数的思路推一下$\sum_{i=1}i^3$
首先$i^3=i^3-i+i=i(i^2-1)+i=(i-1)\cdot i\cdot(i+1)+i$，因此： $$\sum_{i=1}i^3=\sum_{i=1}((i-1)\cdot i\cdot(i+1)+i)=\sum_{i=1}^n (i-1)\cdot i\cdot(i+1)+\sum_{i=1}^n i\\=\frac{1}{4}\sum_{i=1}^n(i-1)\cdot i\cdot(i+1)\cdot 4+\sum_{i=1}^ni=\frac{1}{4}\sum_{i=1}^n(i-1)\cdot i\cdot(i+1)\cdot((i+2)-(i-2))+\sum_{i=1}^ni\\=\frac{1}{4}\sum_{i=1}^n(-(i-2)\cdot(i-1)\cdot i\cdot(i+1)+(i-1)\cdot i\cdot(i+1)\cdot(i+2))+\sum_{i=1}^n i\\=\frac{1}{4}(-(-1)\cdot 0\cdot 1\cdot 2+0\cdot1\cdot2\cdot3-0\cdot1\cdot2\cdot3+1\cdot2\cdot3\cdot4-1\cdot2\cdot3\cdot4+\cdots+(n-1)\cdot n\cdot(n+1)\cdot(n+2))+\sum_{i=1}^n i\\=\frac{1}{4}(n-1)\cdot n\cdot(n+1)\cdot(n+2)-\frac{n\cdot(n+1)}{2}\\=\frac{n\cdot(n+1)\cdot((n-1)\cdot(n+2))}{4}+\frac{n\cdot(n+1)\cdot 2}{4}\\=\frac{n\cdot(n+1)\cdot(n^2+n-2)+n\cdot(n+1)\cdot 2}{4}\\=\frac{n\cdot(n+1)(n^2+n-2+2)}{4}\\=\frac{n\cdot(n+1)\cdot(n\cdot(n+1))}{4}\\=\frac{n^2\cdot(n+1)^2}{4}$$
那么$\sum_{i=1}^ni^2$肯定也很显然了，就不推了，最终的式子为$\frac{n\cdot(n+1)\cdot(2n+1)}{6}$
代入杜教筛的式子得： $$S(n)=\frac{n^2\cdot(n+1)^2}{4}-\sum_{i=2}^n i^2\cdot S(\lfloor\frac{n}{i}\rfloor)=sum(n)^2-\sum_{i=2}^n i^2\cdot S(\lfloor\frac{n}{i}\rfloor)$$
用数论分块和递归可以在很快的时间内用$\sum_{i=1}^ni^2=\frac{n\cdot(n+1)\cdot(2n+1)}{6}$计算出$\sum_{i=2}^n i^2\cdot S(\lfloor\frac{n}{i}\rfloor)$
然后预处理一些$S(n)$就可以了
最后代入原式： $$\sum_{i=1}^n\sum_{j=1}^n i\cdot j\cdot\gcd(i,j)=\sum_{i=1}^n sum(\lfloor\frac{n}{t}\rfloor)\cdot f(t)$$
然后数论分块就结束了

代码：

#include<stdio.h>
#include<map>
using namespace std;
const long long maxn=5000005;
long long i,j,k,m,n,mod,cnt,inv6;
long long a[maxn],p[maxn],varphi[maxn],S[maxn];
map<long long,long long>ans;
inline long long getsum(long long n){
    return n*(n+1)/2%mod;
}
inline long long calc(long long n){
    return n*(n+1)%mod*(2*n+1)%mod*inv6%mod;
}
long long ksm(long long a,long long b,long long mod){
    long long res=1;
    while(b){
        if(b&1)
            res=(res*a)%mod;
        a=(a*a)%mod,b>>=1;
    }
    return res;
}
long long getS(long long n){
    if(n<maxn)
        return S[n];
    if(ans.count(n))
        return ans[n];
    long long l=2,r,res=getsum(n)*getsum(n)%mod;
    while(l<=n){
        r=n/(n/l);
        res=((res-(calc(r)-calc(l-1)+mod)%mod*getS(n/l)%mod)%mod+mod)%mod;
        l=r+1;
    }
    res=(res%mod+mod)%mod;
    return ans[n]=res;
}
long long getans(long long n){
    long long l=1,r,res=0;
    while(l<=n){
        r=n/(n/l);
        res=(res+(getS(r)-getS(l-1)+mod)%mod*getsum(n/l)%mod*getsum(n/l)%mod)%mod;
        l=r+1;
    }
    res=(res%mod+mod)%mod;
    return res;
}
int main(){
    scanf("%lld%lld",&mod,&n);
    inv6=ksm(6,mod-2,mod);
    p[1]=varphi[1]=1;
    for(i=2;i<maxn;i++){
        if(p[i]==0)
            a[++cnt]=i,varphi[i]=i-1;
        for(j=1;j<=cnt;j++){
            if(i*a[j]>=maxn)
                break;
            p[i*a[j]]=1;
            if(i%a[j]==0){
                varphi[i*a[j]]=varphi[i]*a[j];
                break;
            }
            varphi[i*a[j]]=varphi[i]*(a[j]-1);
        }
    }
    for(i=1;i<maxn;i++)
        S[i]=(S[i-1]+varphi[i]%mod*i%mod*i%mod)%mod;
    printf("%lld\n",getans(n));
    return 0;
}