正題

題目鏈接:https://www.luogu.com.cn/problem/P4240

---

題目大意

$Q$組數據給出$n,m$求
$$\sum _{i=1}^n\sum _{j=1}^m\phi (i\times j)$$
$1\le Q\le 10^4,1\le n,m\le 10^5$

---

解題思路

首先需要知道的結論就是
$$\phi (i\times j)=\phi (i)\phi (j)\frac{gcd(i,j)}{\phi (gcd(i,j))}$$

然后推一下式子
$$\sum _{i=1}^n\sum _{j=1}^m\phi (i)\phi (j)\frac{gcd(i,j)}{\phi (gcd(i,j))}$$
$$\sum _{d=1}^n\frac{d}{\phi (d)}\sum _{d|i}^n\sum _{d|j}^m\phi (i)\phi (j)[gcd(i,j)=d]$$
然后莫反一波
$$\sum _{d=1}^n\frac{d}{\phi (d)}\sum _{z|d}^n\mu (\frac{z}{d})\sum _{z|i}^n\sum _{z|j}^m\phi (i)\phi (j)$$
提出$z$來
$$\sum _{z=1}^n(\sum _{z|i}^n\phi (i)\sum _{z|j}^m\phi (j))\sum _{d|z}\mu (\frac{z}{d})\frac{d}{\phi (d)}$$
后面那個很好求，線性篩然后$O(n\log n)$處理就好了，并且設為$g_i$，后面需要用到。但是前面那個比較麻煩，而且我們好像就推不動了。

這其實是一個挺經典的$track$的，考慮平衡規劃。設定一個$T$，對于小于等于$T$的部分我們暴力算，對于大于$T$的部分我們考慮預處理。

設$f_{i,j}={\sum }_{j|x}^i\phi (x)$，然后再設一個$h_{i,j,k}$
$$h_{i,j,k}=\sum _{x=T+1}{f}_{i,j}\times f_{i,k}\times g_i$$
這個可以用一個前綴和$O(n{\frac{n}{T}}^2)$的做到。

然后大于$T$的部分我們就可以用上面預處理的$h$+整除分塊做到$O(\sqrt{n})$了。

總共的時間復雜度是$O(n\sqrt{n}+n{T}^2+Q(T+\sqrt{n}))$
將$T$設為$n^{\frac{2}{3}}$就是$O(n\sqrt{n}+n^{\frac{4}{3}}+Q{n}^{\frac{2}{3}})$了。

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<cmath> #define ll long long using namespace std; const ll N=1e5+10,P=998244353; ll Q,n,m,cnt,pri[N],inv[N],mu[N],phi[N],g[N],o[N]; bool v[N];vector<ll> f[N],h[N]; void prime(){phi[1]=mu[1]=1;for(ll i=2;i<N;i++){if(!v[i])pri[++cnt]=i,phi[i]=i-1,mu[i]=-1;for(ll j=1;j<=cnt&&i*pri[j]<N;j++){v[i*pri[j]]=1;if(i%pri[j]==0){phi[i*pri[j]]=phi[i]*pri[j];break;}phi[i*pri[j]]=phi[i]*(pri[j]-1);mu[i*pri[j]]=-mu[i];}}inv[1]=1;for(ll i=2;i<N;i++)inv[i]=P-(P/i)*inv[P%i]%P;for(ll i=1;i<N;i++)for(ll j=i;j<N;j+=i)(g[j]+=inv[phi[i]]*i%P*mu[j/i])%=P;return; } signed main() {prime();ll L=1e5,T=(ll)pow(L,2.0/3.0)+1;f[0].resize(L+1);for(ll i=1;i<=L;i++){f[i].resize(L/i+1);for(ll j=1;j<=L/i;j++)f[i][j]=(f[i][j-1]+phi[i*j])%P;}h[T].resize((L/T)*(L/T)+1);for(ll i=T+1;i<=L;i++){ll p=L/i;h[i].resize(p*p+1);for(ll j=1;j<=p;j++)for(ll k=1;k<=p;k++)h[i][(j-1)*p+k]=(h[i-1][(j-1)*o[i-1]+k]+f[i][j]*f[i][k]%P*g[i]%P)%P;o[i]=p;}scanf("%lld",&Q);while(Q--){scanf("%lld%lld",&n,&m);if(n>m)swap(n,m);ll ans=0;for(ll i=1;i<=min(T,n);i++)(ans+=f[i][n/i]*f[i][m/i]%P*g[i]%P)%=P;for(ll l=T+1,r;l<=n;l=r+1){r=min(n/(n/l),m/(m/l));(ans+=h[r][(n/l-1)*o[r]+m/l]-h[l-1][(n/l-1)*o[l-1]+m/l])%=P;}printf("%lld\n",(ans+P)%P);}return 0; }

總結

以上是生活随笔為你收集整理的P4240-毒瘤之神的考验【莫比乌斯反演,平衡规划】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。