[CmdOI2019]简单的数论题
题意即求：
\[\sum _ { i= 1 } ^ { n } \sum _ { j = 1 } ^ { m } \varphi \left( \dfrac { \operatorname{lcm} ( i , j) } { \gcd ( i ,j) } \right) \pmod { 23333 } \]其中 \(T \le 3 \times 10 ^ 4\)，$m\le n\le 5 \times 10 ^ 4 $。
此题需要按不同值域分类处理，对复杂度的降低类似分块的想法。
首先推导：
\[\begin{aligned} & \sum _ { i= 1 } ^ { n } \sum _ { j = 1 } ^ { m } \varphi \left( \dfrac { \operatorname{lcm} ( i , j) } { \gcd ( i ,j) } \right) \\ = & \sum _ { i= 1 } ^ { n } \sum _ { j = 1 } ^ { m } \varphi \left( \dfrac { i} { \gcd ( i ,j) } \dfrac { j} { \gcd ( i ,j) }\right) \\ = & \sum _ { i= 1 } ^ { n } \sum _ { j = 1 } ^ { m } \varphi \left( \dfrac { i} { \gcd ( i ,j) } \right) \varphi \left( \dfrac { j} { \gcd ( i ,j) } \right) \\ = & \sum _ {d = 1} \sum _ { i= 1 } ^ { n } \sum _ { j = 1 } ^ { m } \left[ \gcd (i , j) = d \right]\varphi \left( \dfrac { i} { d } \right) \varphi \left( \dfrac { j} { d } \right) \\ = & \sum _ {d = 1} \sum _ { i= 1 } ^ { \left\lfloor n/d \right\rfloor} \sum _ { j = 1 } ^ { \left\lfloor m/d \right\rfloor } \varphi \left( i \right) \varphi \left( j \right) \left[ \gcd (i , j) = 1 \right] \\ = & \sum _ {d = 1} \sum _ { i= 1 } ^ { \left\lfloor n/d \right\rfloor} \sum _ { j = 1 } ^ { \left\lfloor m/d \right\rfloor } \varphi \left( i \right) \varphi \left( j \right) \sum _ { k \mid i, k \mid j} \mu ( k ) \\ = & \sum _ {d = 1} \sum _ { k = 1 } \mu ( k ) \sum _ { i= 1 } ^ { \left\lfloor n/kd \right\rfloor} \sum _ { j = 1 } ^ { \left\lfloor m/kd \right\rfloor } \varphi \left( ik \right) \varphi \left( jk \right) \\ = & \sum _ {T = 1} \sum _ { d \mid T } \mu ( d ) \sum _ { i= 1 } ^ { \left\lfloor n/T \right\rfloor} \varphi \left( id \right) \sum _ { j = 1 } ^ { \left\lfloor m/T \right\rfloor } \varphi \left( jd \right) \end{aligned} \]看上去就非常恐怖。
先定义 $F ( x , d ) = \sum _ { i = 1 } ^ { x } \varphi ( id ) $。
注意到有 \(xd \le n\)，那么 \(F ( x, d )\) 的数量是在 \(O( n \ln n )\) 的。我们可以开一个 vector 解决掉。处理这部分的复杂度也是 \(O ( n \ln n)\) 的。
接下来处理中间这个大头。
我们定义：
\[G ( x , y , z ) = \sum _ { T = 1 } ^ { z } \sum _ {d \mid T} \mu (d) F(x ,d) F (y, d) \]看起来很奇怪，但是我们可以有：
\[\begin{aligned} & \sum _ {T = 1} \sum _ { d \mid T } \mu ( d ) \sum _ { i= 1 } ^ { \left\lfloor n/T \right\rfloor} \varphi \left( id \right) \sum _ { j = 1 } ^ { \left\lfloor m/T \right\rfloor } \varphi \left( jd \right) \\ = & \sum _ { l , r} G(\left\lfloor n / l \right\rfloor , \left\lfloor m / l \right\rfloor ,r) - G (\left\lfloor n / l \right\rfloor , \left\lfloor m / l \right\rfloor, l - 1) \end{aligned} \]这里 \([l,r]\) 代表在数论分块中 \(\left\lfloor n / l \right\rfloor = \left\lfloor n / r \right\rfloor\) 的一个块。
但是这并没有优化复杂度。
考虑一个数量级 \(B\)。
对于 \(x,y\le B\) 的 \(G(x,y,z)\)，我们预先处理，时间复杂度是 \(O(n B ^2 \ln n)\) 的。
那这样 $ \left\lfloor n / l \right\rfloor \le B$ 的所有 \(l\) 我们都能处理，在查询下的总复杂度就是 \(O(T \sqrt{n})\) 的。
那对于 \(\left\lfloor n / l \right\rfloor > B\) 的所有 \(l\)，我们知道会有 \(l < \left\lfloor n / B \right\rfloor\)，那么这一部分我们直接暴力处理也可以，查询下的总时间复杂度就是 \(O(T(n/B)\ln n)\) 的。
最后总的时间复杂度就是 \(O(n B ^ 2\ln n + T(n/B)\ln n + T \sqrt{n})\)。
采用根号平衡，算出 \(B = \sqrt[3]{T}\)。（这里取的是 \(B = 50\)）
最后得到时间复杂度 \(O(T ^ {2/3}n\ln n+ T \sqrt{n})\)。
代码：
#include<iostream>
#include<cstdio>
#include<vector>
#define ll int
using namespace std;
namespace Ehnaev{
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(10);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
}using Ehnaev::read;using Ehnaev::write;
inline void writeln(ll x) {write(x);putchar(10);}
const ll mo=23333,N=5e4,B=50;
ll T,n,m,ans,cnt;
ll prime[N+5],mu[N+5],phi[N+5];
vector<ll> f[N+5];
ll g[B+5][B+5][N+5];
bool ff[N+5];
inline void Init() {
ff[1]=1;mu[1]=1;phi[1]=1;
for(ll i=2;i<=N;i++) {
if(!ff[i]) {prime[++cnt]=i;mu[i]=mo-1;phi[i]=(i-1)%mo;}
for(ll j=1;j<=cnt&&i*prime[j]<=N;j++) {
ff[i*prime[j]]=1;
if(i%prime[j]==0) {
mu[i*prime[j]]=0;
phi[i*prime[j]]=phi[i]*prime[j]%mo;
break;
}
mu[i*prime[j]]=mu[i]*mu[prime[j]]%mo;
phi[i*prime[j]]=phi[i]*phi[prime[j]]%mo;
}
}
for(ll i=0;i<=N;i++) f[0].push_back(0);
for(ll i=1;i<=N;i++) f[i].push_back(0);
for(ll i=1;i<=N;i++) {
for(ll j=i,cn=1;j<=N;j+=i,cn++) {
f[cn].push_back((f[cn-1][i]+phi[j])%mo);
}
}
for(ll i=1;i<=B;i++) {
for(ll j=1;j<=B;j++) {
for(ll k=1;k*i<=N&&k*j<=N;k++) {
ll tmp=(mu[k]*f[i][k]%mo)*f[j][k]%mo;
for(ll l=k;l*i<=N&&l*j<=N;l+=k) {
g[i][j][l]=(g[i][j][l]+tmp)%mo;
}
}
}
}
for(ll i=1;i<=B;i++) {
for(ll j=1;j<=B;j++) {
for(ll k=1;k*i<=N&&k*j<=N;k++) {
g[i][j][k]=(g[i][j][k-1]+g[i][j][k])%mo;
}
}
}
// for(ll i=1;i<=3;i++) {
// for(ll j=1;j<=3;j++) {
// for(ll k=1;k<=3;k++) {
// printf("g[%d][%d][%d]=%d\n",i,j,k,g[i][j][k]);
// }
// }
// }
}
int main() {
T=read();Init();
while(T--) {
n=read();m=read();ans=0;
for(ll i=1;i*B<=n;i++) {
for(ll j=i;j*B<=n;j+=i) {
ll tmp=(mu[i]*f[n/j][i]%mo)*f[m/j][i]%mo;
ans=(ans+tmp)%mo;
}
}
for(ll i=n/B+1,j;i<=m;i=j+1) {
j=min(n/(n/i),m/(m/i));
ll tmp=(g[n/i][m/i][j]-g[n/i][m/i][i-1]+mo)%mo;
ans=(ans+tmp)%mo;
}
writeln(ans);
}
return 0;
}