给定n组询问，询问(sum_{i=1}^nsum_{j=1}^mvarphi(ij)mod 998244353,T≤10^4,n,m≤10^5)。
解
设(nleq m),显然为约数计数问题，但是式子中没有gcd，于是考虑拆(varphi(ij))，它又有具体的公式，而由容斥原理我们有
[ans=sum_{i=1}^nsum_{j=1}^mvarphi(ij)=sum_{i=1}^nsum_{j=1}^mfrac{varphi(i)varphi(j)gcd(i,j)}{varphi(gcd(i,j))}
]
所以
[ans=sum_{d=1}^nfrac{d}{varphi(d)}sum_{i=1}^nsum_{j=1}^mvarphi(i)varphi(j)(gcd(i,j)==d)
]
于是设
[f(d)=sum_{i=1}^nsum_{j=1}^mvarphi(i)varphi(j)(gcd(i,j)==d)
]
[F(d)=sum_{i=1}^nsum_{j=1}^mvarphi(i)varphi(j)(d|gcd(i,j))=sum_{i=1}^{[n/d]}sum_{j=1}^{[m/d]}varphi(id)varphi(jd)
]
由Mobius反演定理有
[f(d)=sum_{d|x}sum_{i=1}^{[n/x]}sum_{j=1}^{[m/x]}varphi(ix)varphi(jx)mu(x/d)
]
代入有
[ans=sum_{x=1}^nsum_{i=1}^{[n/x]}varphi(ix)sum_{j=1}^{[m/x]}varphi(jx)sum_{d|x}mu(x/d)frac{d}{varphi(d)}
]
注意到最后面可以(O(nlon(n)))维护，用函数(l)，问题在于无法解决中间的一堆(varphi)，现在考虑以谁为自变量维护，注意到每个固定的n/x很少，于是设(g(x,y)=sum_{i=1}^yvarphi(ix)),因为sigma具有递推性，所以不难有(g(x,y)=g(x,y-1)+varphi(xy)),暴力动态数组维护，时间复杂度空间复杂度也才(nlog(n)),现在我们所有的式子都能够维护了，考虑现在如何出解。
显然中间的式子不好维护前缀和，于是只能暴力枚举，算一下时间复杂度，也才(10^9)，于是考虑打表分块，设
[h(a,b,c)=sum_{x=1}^asum_{i=1}^bvarphi(ix)sum_{j=1}^cvarphi(jx)sum_{d|x}mu(x/d)frac{d}{varphi(d)}
]
由于sigma的可递推性，我们不难有
[h(a,b,c)=h(a-1,b,c)+g(a,b) imes g(a,c) imes l(a)
]
于是我们可以先预处理一部分h，不妨把b，c限制在(B)里面，当b，c在所求范围，直接整除分快累加答案，这部分时间复杂度近似(O(Tsqrt{n}))，如果([n/x]>B),就有(x<[n/B])，这部分时间复杂度应该为(O(frac{n}{B}T)),所以累计起来时间复杂度应该为(nlog(n)+nB^2+T(frac{n}{B}+sqrt{n}))，玄学地解决了问题,其实你也感性地理解为以一部分空间换询问的时间。
参考代码：
#include <iostream>
#include <cstdio>
#define il inline
#define ri register
#define ll long long
#define con 60
#define lim 100000
#define yyb 998244353
#define swap(x,y) x^=y^=x^=y
using namespace std;
bool check[lim+1];
int prime[10000],pt,mu[lim+1],
phi[lim+1],inv[lim+1],sxr[lim+1],
*wch[lim+1],*czf[con+1][con+1];
il int min(int,int);
il void prepare(int),read(int&),
pen(int);
int main(){
int lsy,i,j,n,m,ans;
read(lsy),prepare(lim);
while(lsy--){
read(n),read(m);
if(n>m)swap(n,m);ans&=0;
for(i=1;i<=m/con;++i)
(ans+=(ll)wch[i][n/i]*wch[i][m/i]%yyb*sxr[i]%yyb)%=yyb;
for(i=m/con+1;i<=n;i=j+1)
j=min(n/(n/i),m/(m/i)),
(ans+=(czf[n/i][m/i][j]-czf[n/i][m/i][i-1])%yyb)%=yyb;
pen((ans+yyb)%yyb),putchar('
');
}
return 0;
}
il void pen(int x){
if(x>9)pen(x/10);putchar(x%10+48);
}
il int min(int a,int b){
return a<b?a:b;
}
il void read(int &x){
x&=0;ri char c;while(c=getchar(),c<'0'||c>'9');
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}
il void prepare(int n){
int i,j,k,l;
check[1]|=mu[1]|=phi[1]|=true;
for(i=2;i<=n;++i){
if(!check[i])prime[++pt]=i,mu[i]=-1,phi[i]=i-1;
for(j=1;j<=pt&&prime[j]*i<=n;++j){
check[i*prime[j]]|=true;
if(!(i%prime[j])){phi[i*prime[j]]=phi[i]*prime[j];break;}
phi[i*prime[j]]=phi[i]*phi[prime[j]],mu[i*prime[j]]=~mu[i]+1;
}
}inv[1]|=true;
for(i=2;i<=n;++i)inv[i]=-(ll)(yyb/i)*inv[yyb%i]%yyb;
for(i=1;i<=n;++i)
for(j=i;j<=n;j+=i)
(sxr[j]+=(ll)i*inv[phi[i]]*mu[j/i]%yyb)%=yyb;
for(i=1;i<=n;++i){
k=n/i,wch[i]=new int[k+1];
for(j=1,wch[i][0]&=0;j<=k;++j)
wch[i][j]=(wch[i][j-1]+phi[i*j])%yyb;
wch[i][0]=k;
}
for(j=1;j<=con;++j)
for(k=j;k<=con;++k){
l=n/k,czf[j][k]=new int[l+1];
for(czf[j][k][0]&=0,i=1;i<=l;++i)
czf[j][k][i]=(czf[j][k][i-1]+(ll)wch[i][j]*
wch[i][k]%yyb*sxr[i]%yyb)%yyb;
}
}