A21658.毒瘤之神的考验题解
2025-07-29 10:47:35
发布于：广东
大意：求∑
i=1
n
∑
j=1
m
φ(ij) mod 998244353。
比较难想到的数学题。
注意到本题为多组询问，并且n、m不算大，所以可以想到用分块打表的方式优化。
(下面的说明中n和m的大小关系不重要，可以默认n≤m)
首先推公式：
令gcd(i,j)=ξ(i,j)， 那么 φ(ij)=
φ(ξ(i,j))
φ(i)φ(j)ξ(i,j)
莫比乌斯反演，那么原式=
i=1
∑
n
j=1
∑
m
φ(ij)=
i=1
∑
n
j=1
∑
m
φ(ξ(i,j))
φ(i)φ(j)ξ(i,j)
=
z=1
∑
n
φ(z)
z
z∣d
∑
μ(
z
d
)
d∣k
∑
n
φ(k)
d∣k
∑
m
φ(k)
=
d=1
∑
n
z∣d
∑
φ(z)
z
μ(
z
d
)
k=1
∑
⌊
d
n
⌋
φ(dk)
k=1
∑
⌊
d
m
⌋
φ(dk)
不妨记G(i,j)=
k=1
∑
i
φ(jk) (ij≤n)
那么原式转化为
d=1
∑
n
z∣d
∑
φ(z)
z
μ(
z
d
)
G(⌊
d
n
⌋,d)G(⌊
d
m
⌋,d)
注意到G数组由于ij≤n所以实际有用的空间只需要O(n)，于是我们可以用动态数组的方式将10
5
以内的G数组预处理然后存下来，预处理复杂度O(nlogn)。
同样，对于不同的d，
z∣d
∑
φ(z)
z
μ(
z
d
)也是可以预处理出来的。
然后我们考虑怎么询问。
熟悉莫比乌斯反演题目的人应该知道，⌊
d
n
⌋这样的东西的不同取值为O(
n
)种。
我们可以预处理一部分答案：
令
T(n,i,j)=
d=1
∑
n
z∣d
∑
φ(z)
z
μ(
z
d
)
G(i,d)G(j,d) (i,j≤B)
B为我们预处理答案的上界，是待定的，之后根据复杂度可以计算出最优值。
那么我们在⌊
d
n
⌋=i,⌊
d
m
⌋=j时的答案就是T(up,i,j)−T(down−1,i,j)，up表示⌊
d
n
⌋=i,⌊
d
m
⌋=j时d的最大值，down表示⌊
d
n
⌋=i,⌊
d
m
⌋=j时d的最小值，跟那种莫比乌斯反演的模板题的计算前缀和然后差分很像。
但是由于T数组不能开太大，T的空间为O(nB
2
)，所以我们只能在⌊
d
n
⌋,⌊
d
m
⌋≤B时直接调用T数组，每次询问在这一部分的复杂度为O(
n
)。
那么对于⌊
d
n
⌋,⌊
d
m
⌋>B，我们会发现一定有d≤⌊
B
n
⌋，我们可以直接暴力算出这一部分的答案，每次询问复杂度为O(⌊
B
n
⌋)。
所以，我们最终的复杂度为O(nlogn+nB
2
+T(
n
+⌊
B
n
⌋))。
计算一下，发现B=T
3
1
左右的时候能取到较优的复杂度，稍微偏大一点好像比较快一点。
代码还是比较好写的：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define M(x) ((x)>=mod?((x)-mod):(x))
#define For(i,_beg,_end) for(int i=(_beg),i##end=(_end);i<=i##end;++i)
#define Rep(i,_beg,_end) for(int i=(_beg),i##end=(_end);i>=i##end;--i)
template<typename T>T Max(const T &x,const T &y){return x<y?y:x;}
template<typename T>T Min(const T &x,const T &y){return x<y?x:y;}
template<typename T>int chkmax(T &x,const T &y){return x<y?(x=y,1):0;}
template<typename T>int chkmin(T &x,const T &y){return x>y?(x=y,1):0;}
template<typename T>void read(T &x){
T f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
x*=f;
}
typedef long long LL;
const int maxn=100010,B=35,mod=998244353;
int Test,n,m,phi[maxn],mu[maxn],prime[maxn],cnt;
int *G[maxn],F[maxn],*T[B+1][B+1],inv[maxn];
bool ok[maxn];
void Init(int n){
mu[1]=phi[1]=inv[1]=1;
For(i,2,n){
if(!ok[i]){
prime[++cnt]=i;
mu[i]=-1;phi[i]=i-1;
}
for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
ok[i*prime[j]]=true;
if(i%prime[j]){
mu[i*prime[j]]=-mu[i];
phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
else{
mu[i*prime[j]]=0;
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
}
}
For(i,2,n) inv[i]=mod-1LL*(mod/i)*inv[mod%i]%mod;
For(i,1,n) for(int j=i;j<=n;j+=i)
F[j]=M(F[j]+M(1LL*mu[j/i]*i*inv[phi[i]]%mod+mod));
For(i,1,n){
G[i]=new int [(n/i)+1];G[i][0]=0;
For(j,1,n/i) G[i][j]=M(G[i][j-1]+phi[i*j]);
}
For(j,1,B) For(k,j,B){
int len=n/Max(j,k);
T[j][k]=new int [len+1];T[j][k][0]=0;
For(i,1,len) T[j][k][i]=M(T[j][k][i-1]+1LL*F[i]*G[i][j]%mod*G[i][k]%mod);
}
}
LL Solve(int n,int m){
if(n>m)swap(n,m);
LL res=0;
For(i,1,m/B) res=M(res+1LL*F[i]*G[i][n/i]%mod*G[i][m/i]%mod);
for(int i=m/B+1,nxt;i<=n;i=nxt+1){
nxt=Min(n/(n/i),m/(m/i));
res=M(res+M(T[n/i][m/i][nxt]-T[n/i][m/i][i-1]+mod));
}
return res;
}
int main(){
read(Test);Init(100000);
while(Test--){
read(n);read(m);
printf("%lld\n",Solve(n,m));
}
return 0;
}
这里空空如也
有帮助，赞一个