【傳送門：BZOJ2154&BZOJ2693】

---

簡要題意：

　　給出n,m，求$\sum_{i=1}^{n}\sum_{j=1}^{m}LCM(i,j)$

---

題解：

　　莫比烏斯反演（因為BZOJ2693是多組數據，數據強一點，所以代碼用BZOJ2693的）

　　設n<m，原式等于$\sum_{i=1}^{n}\sum_{j=1}^{m}i*j/gcd(i,j)$

　　然后枚舉d值作為i和j的gcd，得到$$\sum_{d=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i*j}ze8trgl8bvbq[gcd(i,j)==d]$$

　　因為gcd(i,j)==d，所以gcd(i/d,j/d)==1，得到$$\sum_{d=1}^{n}d*\sum_{i=1}^{\frac{n}ze8trgl8bvbq}\sum_{j=1}^{\frac{m}ze8trgl8bvbq}i*j[gcd(i,j)==1]$$

　　因為莫反的性質：$\sum_{d|x}\mu(d)=[x==1]$，所以轉化為$$\sum_{d=1}^{n}d*\sum_{i=1}^{\frac{n}ze8trgl8bvbq}\sum_{j=1}^{\frac{m}ze8trgl8bvbq}i*j*\sum_{t|gcd(i,j)}\mu(t)$$

　　交換和式得到$$\sum_{d=1}^{n} d* \sum_{t=1}^{\frac{n}ze8trgl8bvbq} \mu(t) * \sum_{i=1}^{\frac{n}ze8trgl8bvbq} \sum_{j=1}^{\frac{m}ze8trgl8bvbq} i*j[gcd(i,j)==t]$$

　　$$\sum_{d=1}^{n}d*\sum_{t=1}^{\frac{n}ze8trgl8bvbq}t^{2}*\mu(t)*\sum_{i=1}^{\frac{n}{dt}}\sum_{j=1}^{\frac{m}{dt}}i*j$$

　　設$T=dt$，$S(x)=\sum_{i=1}^{x}i$，得到$$\sum_{d=1}^{n}\sum_{t=1}^{\frac{n}ze8trgl8bvbq}T*t*\mu(t)*S(\frac{n}{T})*S(\frac{m}{T})$$

　　將$S(\frac{n}{T})*S(\frac{m}{T})$提前，得到$$\sum_{T=1}^{n}T*S(\frac{n}{T})*S(\frac{m}{T})\sum_{d|T}d*\mu(d)$$

　　因為$S(\frac{n}{T})*S(\frac{m}{T})$可以前綴和預處理，顯然我們只要將$\sum_{d|T}d*\mu(d)$快速求出就可以了

　　設$F(T)=\sum_{d|T}d*\mu(d)$，顯然是一個積性函數，在線性篩的時候求就行了

　　然后將$T*F(T)$求前綴和，然后整除分塊加速就能過了

---

參考代碼：

#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; typedef long long LL; int prime[11000000],v[11000000]; LL f[11000000],sum[11000000]; LL Mod=1e8+9; void pre(int n) {f[1]=1;int tot=0;for(int i=2;i<=n;i++){if(v[i]==0){v[i]=i;prime[++tot]=i;f[i]=(1-i+Mod)%Mod;}for(int j=1;j<=tot;j++){if(prime[j]>v[i]||prime[j]>n/i) break;v[i*prime[j]]=prime[j];if(i%prime[j]==0){f[i*prime[j]]=f[i]%Mod;break;}else f[i*prime[j]]=f[i]*f[prime[j]]%Mod;}}for(int i=1;i<=n;i++) f[i]=(f[i]*LL(i)%Mod+f[i-1])%Mod;for(int i=1;i<=n;i++) sum[i]=(sum[i-1]+LL(i))%Mod; } int main() {pre(10000000);int T;scanf("%d",&T);while(T--){int n,m;scanf("%d%d",&n,&m);if(n>m) swap(n,m);LL ans=0;for(int i=1,j;i<=n;i=j+1){j=min(n/(n/i),m/(m/i));ans=(ans+(f[j]-f[i-1]+Mod)%Mod*sum[n/i]%Mod*sum[m/i]%Mod)%Mod;}printf("%lld\n",ans);}return 0; }

?

轉載于:https://www.cnblogs.com/Never-mind/p/9845948.html

總結

以上是生活随笔為你收集整理的BZOJ2154: Crash的数字表格 BZOJ2693: jzptab的全部內容，希望文章能夠幫你解決所遇到的問題。

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