[P4240] 毒瘤之神的考验

题目链接

不妨设\(n\le m\)
\[ \begin{aligned} ans&=\sum_{i=1}^n\sum_{j=1}^m\varphi(ij)\\ &=\sum_{i=1}^n\sum_{j=1}^m\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}\\ &=\sum_{d=1}^{n}\frac{d}{\varphi(d)}\sum_{i=1}^n\sum_{j=1}^m\varphi(i)\varphi(j)[d=\gcd(i,j)] \\ f(d)&=\sum_{i=1}^n\sum_{j=1}^m\varphi(i)\varphi(j)[d=\gcd(i,j)] \\ g(d)&=\sum_{d|x}f(x)\\ &=\sum_{i=1}^n\sum_{j=1}^m\varphi(i)\varphi(j)[d|\gcd(i,j)]\\ &=\sum_{i=1}^{n/d}\varphi(id)\sum_{j=1}^{m/d}\varphi(jd) \\ f(d)&=\sum_{d|x}\mu(\frac{x}d)g(x) \\ ans&=\sum_{d=1}^{n}\frac{d}{\varphi(d)}f(d)\\ &=\sum_{d=1}^{n}\frac{d}{\varphi(d)}\sum_{d|x}\mu(\frac{x}d)g(x)\\ \\ \end{aligned} \]
预处理\(g(d)\)，然后暴力做\(ans\)，复杂度都是\(n\log n\)的。

---

是的这并不能过……
\[ \begin{aligned} ans&=\sum_{d=1}^n\frac{d}{\varphi(d)}\sum_{d|x}\mu(\frac{x}d)\sum_{i=1}^{n/x}\varphi(ix)\sum_{j=1}^{m/x}\varphi(jx)\\ &=\sum_{x=1}^n\sum_{i=1}^{n/x}\varphi(ix)\sum_{j=1}^{m/x}\varphi(jx)\sum_{d|x}\frac{d}{\varphi(d)}\mu(\frac{x}d)\\ g(x,t)&=\sum_{i=1}^t\varphi(ix)\\ &=g(x,t-1)+\varphi(tx)\\ f(x)&=\sum_{d|x}\frac{d}{\varphi(d)}\mu(\frac{x}d)\\ s(n,m,t)&=\sum_{x=1}^tg(x,n/x)g(x,m/x)f(x)\\ &=s(n,m,t-1)+g(t,n/t)g(t,m/t)f(t) \end{aligned} \]
埃氏筛求出\(g,f\)以及一部分的\(s\)，剩下的暴力算。如果设块大小为\(b\)，则预处理、计算的\(s\)复杂度为\(nb^2+t(\sqrt n-\sqrt{n/b} +n/b)\)，然后实践出真知地求出较优的\(b\)。

#include <bits/stdc++.h>
using namespace std;
const int n=1e5;
const int b=40;
const int p=998244353;

bool vis[n+1];
int pri[n+1],phi[n+1],mu[n+1],tot;
int inv[n+1];

int f[n+1],*g[n+1],*s[b+1][b+1];

void initial() {
    phi[1]=mu[1]=1;
    for(int i=2; i<=n; ++i) {
        if(!vis[i]) pri[++tot]=i,phi[i]=i-1,mu[i]=-1;
        for(int j=1; j<=tot&&i*pri[j]<=n; ++j) {
            vis[i*pri[j]]=1;
            if(i%pri[j]==0) {phi[i*pri[j]]=phi[i]*pri[j]; break;}
            phi[i*pri[j]]=phi[i]*(pri[j]-1);
            mu[i*pri[j]]=-mu[i];
        }
    }
    inv[1]=1;
    for(int i=2; i<=n; ++i) inv[i]=1ll*inv[p%i]*(p-p/i)%p;
    for(int i=1; i<=n; ++i) 
    for(int j=1; j<=n/i; ++j) 
        f[i*j]=(f[i*j]+1ll*i*inv[phi[i]]%p*mu[j]%p+p)%p;
    for(int i=1; i<=n; ++i) {
        g[i]=new int[n/i+1];
        g[i][0]=0;
        for(int j=1; j<=n/i; ++j) 
            g[i][j]=(g[i][j-1]+phi[i*j])%p;
    }
    for(int x=1; x<=b; ++x) 
    for(int y=1; y<=b; ++y) {
        int t=n/max(x,y);
        s[x][y]=new int[t+1];
        s[x][y][0]=0;
        for(int t=1; t<=t; ++t) 
            s[x][y][t]=(s[x][y][t-1]+1ll*f[t]*g[t][x]%p*g[t][y]%p)%p;
    }
}

int solve(int n,int m) {
    if(m<n) swap(n,m);
    int ans=0;
    for(int i=1; i<=m/b; ++i) 
        ans=(ans+1ll*f[i]*g[i][n/i]%p*g[i][m/i]%p)%p;
    for(int l=m/b+1,r; l<=n; l=r+1) {
        r=min(n/(n/l),m/(m/l));
        ans=(ans+(s[n/l][m/l][r]-s[n/l][m/l][l-1]+p)%p)%p;
    }
    return ans;
}

int main() {
    initial();
    int t,n,m;
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d",&n,&m);
        printf("%d\n",solve(n,m));
    }
    return 0;
}