计蒜客 2019 ICPC中国南昌网络邀请赛 tsy’s number（莫比乌斯反

计蒜客 2019 ICPC中国南昌网络邀请赛 tsy’s number（莫比乌斯反演+数论分块+线性筛）

题目链接：https://nanti.jisuanke.com/t/38226
题目大意：给定T组正整数n，求 $\sum _{i=1}^n\sum _{j=1}^n\sum _{k=1}^n\frac{\phi (i)\phi (j^2)\phi (k^3)}{\phi (i)\phi (j)\phi (k)}\phi (gcd(i,j,k))mod{2}^{30}$ 的值。
题解：看着很唬人，其实还是有套路的。。。
原式：$\sum _{i=1}^n\sum _{j=1}^n\sum _{k=1}^n\frac{\phi (i)\phi (j^2)\phi (k^3)}{\phi (i)\phi (j)\phi (k)}\phi (gcd(i,j,k))$
$=\sum _{i=1}^n\sum _{j=1}^n\sum _{k=1}^{n}j{k}^2\phi (gcd(i,j,k))$
$=\sum _{i=1}^n\sum _{j=1}^n\sum _{k=1}^{n}j{k}^2\sum _{d=1}^n\phi (d)[gcd(i,j,k)=d]$
$=\sum _{d=1}^n\phi (d)d^3\sum _{i=1}^{?\frac{n}{d}?}\sum _{j=1}^{?\frac{n}{d}?}\sum _{k=1}^{?\frac{n}{d}?}j{k}^2[gcd(i,j,k)=1]$
$=\sum _{d=1}^n\phi (d)d^3\sum _{i=1}^{?\frac{n}{d}?}\sum _{j=1}^{?\frac{n}{d}?}\sum _{k=1}^{?\frac{n}{d}?}j{k}^2\epsilon (gcd(i,j,k))$
$=\sum _{d=1}^n\phi (d)d^3\sum _{i=1}^{?\frac{n}{d}?}\sum _{j=1}^{?\frac{n}{d}?}\sum _{k=1}^{?\frac{n}{d}?}j{k}^2\sum _{t\mid i,t\mid j,t\mid k}\mu (t)$
$=\sum _{d=1}^n\phi (d)d^3\sum _{t=1}^{?\frac{n}{d}?}\mu (t)t^3\sum _{i=1}^{?\frac{n}{dt}?}\sum _{j=1}^{?\frac{n}{dt}?}\sum _{k=1}^{?\frac{n}{dt}?}j{k}^2$
令 $f(x)=\sum _{t=1}^x\mu (t)t^3\sum _{i=1}^{?\frac{x}{t}?}\sum _{j=1}^{?\frac{x}{t}?}\sum _{k=1}^{?\frac{x}{t}?}j{k}^2$ ，函数前半部分的 $\mu (t)t^3$ 可以利用前缀和数组求值，后半部分可以利用数论分块加速。那么可以令原式为函数 $g(x)$ ，则有 $g(x)=\sum _{d=1}^x\phi (x)x^{3}f(?\frac{x}{d}?)$ ，同样的，这个函数的前半部分可以通过前缀和求出，后半部分也可以利用数论分块加速。
下面是AC代码。

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<":"<<x<<"  "<<#y<<":"<<y<<endl
#define debug3(x,y,z) cerr<<#x<<":"<<x<<"  "<<#y<<":"<<y<<"  "<<#z<<":"<<z<<endl
typedef long long ll;
struct fastio{
    fastio(){
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
}fio;
const int N=1e7+5;
const int M=1<<30;
const int INV3=1789569707;
vector<int> prime,part,mu,s1,s2,phi;
void init(){
    phi=s1=s2=part=vector<int>(N,0);
    mu=vector<int>(N,-1);
    s1[1]=s2[1]=phi[1]=mu[1]=1;
    for(ll i=2;i<N;++i){
        s2[i]=((((ll)mu[i]*i*i)%M*i)%M+M+(ll)s2[i-1])%M;
        if(!part[i]){
            prime.push_back(i);
            part[i]=i;
            phi[i]=i-1;
        }
        s1[i]=((((((ll)phi[i]*i)%M)*i)%M*i)%M+(ll)s1[i-1])%M;
        for(auto j:prime){
            if(i*j>=N) break;
            part[i*j]=j;
            if(i%j==0){
                mu[i*j]=0;
                phi[i*j]=((ll)j*(ll)phi[i])%M;
                break;
            }
            else{
                mu[i*j]=-mu[i];
                phi[i*j]=((ll)phi[i]*(ll)phi[j])%M;
            }
        }
    }
}
unordered_map<int,int> f_v;
ll f(ll x){
    if(f_v[x]) return f_v[x];
    ll res=0;
    for(ll l=1,r;l<=x;l=r+1){
        r=x/(x/l);
        ll y=((ll)(1+x/l)*(x/l)>>1ll)%M;
        res=(res+((s2[r]-s2[l-1])%M*((ll)(x/l)*y%M*y%M*(((ll)(x/l)<<1ll)+1)%M*INV3%M)+M)%M)%M;
    }
    return f_v[x]=res;
}
int g(ll x){
    int res=0;
    for(ll l=1,r;l<=x;l=r+1){
        r=x/(x/l);
        res=((res+(ll)(s1[r]-s1[l-1])%M*f(x/l)%M)%M+M)%M;
    }
    return res;
}
signed main(){
    int t,n;
    cin>>t;
    init();
    while(t--){
        cin>>n;
        cout<<g(n)<<endl;
    }
}

要注意的是，我们可以利用map对 $f(x)$ 的值进行储存，避免不必要的计算（如果不用map会TLE的说）。同时结果要返回正整数值，否则会WA。

（勉勉强强卡过了吧。。。）