洛谷P3768 简单的数学题

好神仙的数学题呀，感觉涨了很多知识。

传送门

求$∑{i=1}^n∑{j=1}^nijgcd(i,j)$

先上反演套路：
$$
\sum_{i=1}^ni\sum_{j=1}^nj\sum_{d=1}^{n}[gcd(i,j)=d]\times d
$$
整理下式子
$$
\sum_{d=1}^{n}d\sum_{i=1}^{n/d}i\sum_{j=1}^{n/d}j[gcd(i,j)=1]
$$

反演
$$
\sum_{d=1}^{n}d\sum_{i=1}^{n/d}i\times d\sum_{j=1}^{n/d}j\times d\sum_{k|i,k|j}\mu(k)
$$
把k提到前面，枚举k的倍数
$$
\sum_{d=1}^{n}d^3\sum_{k=1}^{n/d}\mu(k)\sum_{i=1}^{n/dk}i\times k\sum_{j=1}^{n/dk}j\times k
$$
枚举T=dk
$$
\sum_{T=1}^n\sum_{d|T}d^3\times (\frac{T}{d})^2\times\mu(\frac{T}{d})\sum_{i=1}^{n/T}i\sum_{j=1}^{n/T}j
$$
整理一下，（中间$k^2$那里有点跳步，不过应该无伤大雅）
$$
\sum_{T=1}^nT^2\sum_{d|T}d\times\mu(\frac{T}{d})\sum_{i=1}^{n/T}i\sum_{j=1}^{n/T}j
$$
这样你就有了一个60分的反演做法，不过如果你像我一样SB的话分数会在10~60不定。

这个式子显然后面整除分块，前面线筛+埃筛筛出$f(T)=T^2\sum_{d|T}d\times \mu(d)$的前缀和即可，是$n\ logn​$的。

但是其实$\sum_{d|T}d\times\mu(\frac{T}{d})$等于欧拉函数，也就是$id*\mu=\phi​$。我今天才知道

那么你就可以丢掉埃筛的log，$O(n)$做了，好的还是60分。

不过$f(x)=x^2\phi(x)$看起来就可以杜教筛。

上杜教筛公式（h(x)表示卷积的前缀和，g(x)表示杜教筛用的那个函数，s(x)表示f(x)的前缀和）：
$$
g(1)s(n)=\sum_{i=1}^nh(i)-\sum_{i=2}^ng(i)s(\frac{n}{i})
$$
g我们取$id^2$，那么有
$$
\sum_{i=1}^nh(i)=\sum_{i=1}^n\sum_{d|i}d^2\times\phi(d)\times(\frac{i}{d})^2\

=\sum_{i=1}^ni^2\times\sum_{d|i}\phi(d)
$$
而你所不知道的是，$\phi\times 1=id​$ 我今天才知道

那么
$$
\sum_{i=1}^nh(i)=\sum_{i=1}^ni^3=(\frac{n\times(n+1)}{2})^2
$$
这个东西是个公式，我太菜了，没上过小学，但我会打表：

$1^3=1^2$

$1^3+2^3=9=3^2=(1+2)^2 $

$1^3+2^3+3^3=36=6^2=(1+2+3)^2$

$1^3+2^3+3^3+…+n^3=(1+2+3+…+n)^2$

好的那我们只有最后一个问题了，求$\sum_{i=1}^ni^2$，这个我会！！！，是$\frac{n\times\ (n+1)\times (2n+1)}{6}$。

恭喜你，通过了本题。

ps:然而并没有上面说的那么简单，你要小心这些错误：

for (int i=1; i<=blo; i++) phi[i]=i*i%mod*phi[i]%mod;

应该乘上1LL

ll num=x*(x+1)%mod*inv[2]%mod;

换成一般题看起来很正常对吧，但是x范围是1e10，就是说你必须写一个变量加一个%mod

还有，线性筛预处理的阈值开到1e7是最快的，2e6就是个弟弟。

#include<map>
#include<cmath>
#include<cstdio>
#include<iostream>
#include <tr1/unordered_map>
#define ll long long
using namespace std;
using namespace tr1;
ll n,mod,blo,ans,inv[7],phi[10000011];
int o[10000011],prime[5000010];
inline void euler(){
    o[1]=phi[1]=1;
    for (int i=2; i<=blo; i++){
        if (!o[i]){
            o[i]=1; prime[++prime[0]]=i; phi[i]=i-1;
        }
        for (int j=1; j<=prime[0]&&prime[j]*i<=blo; j++){
            o[i*prime[j]]=1;
            if (i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j]%mod;
                break;
            }
            phi[i*prime[j]]=phi[i]*phi[prime[j]]%mod;
        }
    }
    for (int i=1; i<=blo; i++) phi[i]=1LL*i*i%mod*phi[i]%mod;
    for (int i=1; i<=blo; i++) phi[i]=(phi[i]+phi[i-1])%mod;
}
unordered_map<ll,ll> m;
ll get_phi(ll x){
    if (x<=blo) return phi[x];
    // puts("ok");
    if (m[x]) return m[x];
    ll num=x%mod*(x+1)%mod*inv[2]%mod; num=num*num%mod;
    ll cl,cr;
    for (ll l=2,r; l<=x; l=r+1){
        r=x/(x/l);
        cl=(2*l-1)%mod*l%mod*(l-1)%mod*inv[6]%mod;
        cr=(2*r+1)%mod*r%mod*(r+1)%mod*inv[6]%mod;
        num=(num-(cr-cl)%mod*get_phi(x/l)%mod)%mod;
    }
    num=(num+mod)%mod; m[x]=num;
    return num;
}
int main(){
    scanf("%lld%lld",&mod,&n);
    blo=1e7; blo=min(blo,n); euler(); inv[1]=1;
    for (int i=2; i<=6; i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    // for (int i=1; i<=n; i++){
    // 	ans=(ans+1LL*phi[i]*sum[n/i]%mod*sum[n/i]%mod)%mod;
    // }
    ll a,b;
    for (ll l=1,r; l<=n; l=r+1){
        r=n/(n/l); ll m=n/l;
        a=(get_phi(r)-get_phi(l-1))%mod,b=(m+1)%mod*m%mod*inv[2]%mod;
        b=b*b%mod; ans=(ans+b*a%mod)%mod;
    }
    printf("%lld\n",(ans+mod)%mod);
    return 0;
}