$T$ 组数据,求 $\sum_{i=1}^n\sum_{j=1}^m \varphi(ij)\mod 998244353$。

$T\leq10^4,n,m\leq 10^5$。

这题越细想/写越觉得毒瘤,最后一步均摊复杂度挺妙的。

用 $\varphi(ij)=\frac{\varphi(i)\varphi(j)(i,j)}{\varphi((i,j))}$ 大力推一波柿子。

$$ ans=\sum_{T=1}^n\sum_{d|T}\frac{d}{\varphi(d)}\mu(\frac{T}{d})\sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}\varphi(iT)\sum_{j=1}^{\lfloor\frac{m}{T}\rfloor}\varphi(jT) $$

首先解决前面那坨,记 $f_n=\sum_{d|n}\frac{d}{\varphi(d)}\mu(\frac{n}{d})$,首先这显然是个积性函数,简单手玩一下就可以得到:$f_p=\frac{1}{p-1},f_{p^q(q≥2)}=0$。于是就可以愉快的 $O(n)$ 线性筛出来。当然,这个东西也可以 $O(n\ln n)$ 预处理,对复杂度没有影响。

考虑设 $g(i,j)=\sum_{k=1}^j\varphi(ik)$,显然我们对于一个 $i$ ,它需要的 $j$ 共 $\lfloor\frac{n}{i}\rfloor$ 个,总个数是 $O(n\ln n)$ 的,可以预处理到一个 $vector$ 里面。

于是就有 $ans=\sum_{i=1}^nf(i)g(i,\lfloor\frac{n}{i}\rfloor)g(i,\lfloor\frac{m}{i}\rfloor)$,长成这个样子就想让我整除分块,然后我就傻了,这玩意是三个乘积的形式,完全没法直接分。

于是为了整除分块,我们记 $T(l,a,b)=\sum_{i=1}^lf(i)g(i,a)g(i,b)$,$T(l,a,b)=T(l-1,a,b)+f(l)g(l,a)g(l,b)$。

如果我们有所有的这玩意,差分一下,整除分块就只和第一个参数有关了,但是很明显我们是无法求出所有的 $T$ 值的,于是我们考虑如何均摊复杂度。

设我们预处理 $a,b$ 两个维度到 $S$,也就是我们预处理 $T_{1...n,1...S,1...S}$,时间复杂度 $O(nS^2)$。

没有预处理的部分我们当然就暴力算。考虑没有被预处理到的部分就是 $\lfloor\frac{n}{i}\rfloor>S$ 的,于是就有 $i\leq \lfloor \frac{n}{S} \rfloor $, 暴力做的话每组询问的时间复杂度就是 $O(\lfloor \frac{n}{S}\rfloor)$,这一步的时间复杂度就是 $O(nS^2+T(\sqrt n+\lfloor \frac{n}{S}\rfloor))$,调一下参就过了。

#include<bits/stdc++.h>
#define reg register
#define pb push_back
#define int long long
#define For(i,a,b) for(reg int i=(a),i##END=(b);i<=i##END;i++)
#define Rof(i,b,a) for(reg int i=(b),i##END=(a);i>=i##END;i--)
#define go(u) for(reg int i=head[u];i;i=nxt[i])
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
const int N=1e5+10;
int pr[N],f[N],phi[N],st[N],cnt;
const int p=998244353;
inline int inv(int a,int b=p-2){
    int x=1;
    while(b){
        if(b&1)(x*=a)%=p;
        (a*=a)%=p,b>>=1;
    }
    return x;
}
void get(int n=N-10){
    f[1]=1,phi[1]=1,cnt=0;
    For(i,2,n){
        if(!st[i])pr[++cnt]=i,phi[i]=i-1,f[i]=inv(i-1);
        for(int j=1;j<=cnt&&pr[j]*i<=n;j++){
            st[i*pr[j]]=1;
            if(i%pr[j]==0){
                phi[i*pr[j]]=phi[i]*pr[j];
                break;
            }
            phi[i*pr[j]]=phi[i]*(pr[j]-1);
            f[i*pr[j]]=f[i]*f[pr[j]]%p;
        }
    }
}
vector<int> g[N];
const int S=20;
int T[N][S][S]; 
signed main(){
    get();
    int n,m;
    n=N-10;
    For(i,1,n){
        int now=0;g[i].pb(now);
        For(j,1,n/i)(now+=phi[j*i])%p,g[i].pb(now);
    }
    For(i,1,n)For(a,1,S-1)For(b,1,S-1)if(a<=n/i&&b<=m/i)T[i][a][b]=(T[i-1][a][b]+f[i]*g[i][a]%p*g[i][b]%p)%p;else break;
    int t=read();
    while(t--){
        reg int n=read(),m=read(),res=0;
        if(n>m)n^=m^=n^=m;
//        For(i,1,n)(res+=f[i]%p*g[i][n/i]%p*g[i][m/i]%p)%=p;
        for(int l=1,r;l<=n;l=r+1){
            int A=n/l,B=m/l;
            r=min(n,min(n/A,m/B));
            if(A<S&&B<S)(res+=(T[r][A][B]-T[l-1][A][B]+p)%p)%=p;
            else For(i,l,r)(res+=f[i]%p*g[i][A]%p*g[i][B]%p)%=p;
        }
        printf("%d\n",res);
    }
    return 0;
}
最后修改:2021 年 04 月 29 日 09 : 10 PM