题目大意：略
果然是一道神duliu题= =
出题人的题解还是讲得很明白的
1.关于$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\varphi (i,j)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\frac{\varphi (i)\varphi (j)gcd(i,j)}{\varphi (gcd(i,j))}$的证明，lgl神犇提供了一种方法
假设现在$gcd(i,j)$中有一个质因子$p$，幂次是$k$，那么它对$\varphi (gcd(i,j))$的贡献就是$p^{k-1}(p-1)$
设$i$中$p$的幂次是$k_{1}$，$j$是$k_{2}$。则他们对$\varphi (i),\varphi (j)$的贡献分别是$p^{k_{1}-1}(p-1)$和$p^{k_{2}-1}(p-1)$，相乘得$p^{k_{1}+k_{2}-2}(p-1)^{2}$
而$p$对$\varphi (ij)$的贡献是$p^{k_{1}+k_{2}-1}(p-1)$，所以$\frac{p^{k}}{p^{k-1}(p-1)}=\frac{p}{p-1}$
$\frac{p}{p-1}*p^{k_{1}+k_{2}-2}(p-1)^{2}=p^{k_{1}+k_{2}-1}(p-1)$
而质因子间互不影响，因此得证
2.对于最后化简出来的式子$\sum\limits_{Q=1}^{n} \left ( \sum\limits_{d|Q}\frac{d}{\varphi (d)}\mu(\frac{Q}{d}) \right ) \left ( \sum\limits_{i=1}^{\left \lfloor \frac{n}{Q} \right \rfloor} \varphi (iQ) \right ) \left ( \sum\limits_{i=1}^{\left \lfloor \frac{m}{Q} \right \rfloor} \varphi (jQ) \right )$ 的处理
整除分块不能同时处理两个定义域不同的函数相乘！
所以要把第一个式子$\left ( \sum\limits_{d|Q}\frac{d}{\varphi (d)}\mu(\frac{Q}{d}) \right )$ 按照常规方法进行整除分块，第二个式子$\left ( \sum\limits_{i=1}^{\left \lfloor \frac{n}{Q} \right \rfloor} \varphi (iQ) \right ) $和$\left ( \sum\limits_{i=1}^{\left \lfloor \frac{m}{Q} \right \rfloor} \varphi (jQ) \right )$用官方题解的方法处理
蒟蒻用$vector$写的常数巨大
1 #include2 #include 3 #include 4 #include 5 #define N1 100010 6 #define ll long long 7 #define dd double 8 using namespace std; 9 10 const int B=31;11 const int maxn=100000;12 const int jr=998244353;13 14 void exgcd(ll a,ll b,ll &x,ll &y)15 {16 if(!b){ x=1; y=0; return; }17 exgcd(b,a%b,x,y); ll t=x; x=y; y=t-a/b*y; 18 }19 int mu[N1],phi[N1],use[N1],pr[N1],cnt;20 int f[N1],G[N1][B+1][B+1];21 vector g[N1];22 void init()23 {24 int i,j,Q,n; mu[1]=phi[1]=1;25 for(i=2;i<=maxn;i++)26 {27 if(!use[i]){ pr[++cnt]=i; mu[i]=-1; phi[i]=i-1; }28 for(j=1;j<=cnt&&i*pr[j]<=maxn;j++)29 {30 use[i*pr[j]]=1;31 if(i%pr[j]){ mu[i*pr[j]]=-mu[i]; phi[i*pr[j]]=phi[i]*phi[pr[j]]; }32 else{ phi[i*pr[j]]=phi[i]*pr[j]; break; }33 }34 }35 int ans=0;ll inv,y;36 for(Q=1;Q<=maxn;Q++)37 {38 ans=0;39 for(i=1;i*Q<=maxn;i++)40 {41 ans=(phi[i*Q]+ans)%jr;42 g[Q].push_back(ans);43 }44 }45 for(i=1;i<=maxn;i++)46 {47 exgcd(phi[i],jr,inv,y); inv=(inv%jr+jr)%jr;48 for(j=1;j*i<=maxn;j++)49 f[i*j]=(1ll*i*inv%jr*mu[j]%jr+f[i*j]+jr)%jr;50 //sf[i]=(sf[i-1]+f[i])%jr;51 }52 for(Q=1;Q<=maxn;Q++)53 {54 for(i=1;i<=B;i++) for(j=1;j<=B;j++)55 G[Q][i][j]=(1ll*g[Q][i-1]*g[Q][j-1]%jr*f[Q]+G[Q-1][i][j])%jr;56 }57 }58 int n,m,T;59 60 int main()61 {62 scanf("%d",&T);63 init();64 int i,j,la;ll ans=0;65 while(T--)66 {67 scanf("%d%d",&n,&m); if(n>m) swap(n,m);68 for(i=1,ans=0;i<=n&&m/i>B;i++)69 ans=(ans+1ll*g[i][n/i-1]*g[i][m/i-1]%jr*f[i]%jr)%jr;70 for(;i<=n;i=la+1)71 {72 la=min(n/(n/i),m/(m/i));73 ans=(ans+G[la][n/i][m/i]-G[i-1][n/i][m/i]+jr)%jr; 74 }75 printf("%lld\n",ans);76 }77 return 0;78 }