[SDOI2015]約數個數和

題目描述

設\(d(x)\)為\(x\)的約數個數，給定\(N,M\)，求$ \sum\limits^N_{i=1}\sum\limits^M_{j=1}d(ij)$

輸入輸出格式

輸入格式：

輸入文件包含多組測試數據。第一行，一個整數\(T\)，表示測試數據的組數。接下來的\(T\)行，每行兩個整數\(N,M\)。

輸出格式：

\(T\)行，每行一個整數，表示你所求的答案。

說明

\(1 \le N, M \le 50000\)

\(1 \le T \le 50000\)

---

Solution

引理\(1\)：

\[\sum_{d|gcd(a,b)} \mu(d)=[gcd(a,b)=1]\]

引理\(2\):

\[d(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]\]

可以通過\(d\)唯一分解后的計算式感性理解一下

剩下的暴力推個式子

\[\sum_{i=1}^a\sum_{j=1}^bd(ij)\]

\[=\sum_{i=1}^a\sum_{j=1}^b\sum_{x|i}\sum_{y|j}\sum_{d|gcd(x,y)}\mu(d)\]

暴力更換不太好枚舉的一些東西（比如誰整除誰）

\[=\sum_{i=1}^a\sum_{j=1}^b\sum_{x|i}\sum_{y|j}\sum_{d=1}^{min(a,b)}\mu(d)[d|gcd(x,y)]\]

\[=\sum_{d=1}^{min(a,b)}\mu(d)\sum_{i=1}^a\sum_{j=1}^b\sum_{x|i}\sum_{y|j}[d|gcd(a,b)]\]

調整求和順序

\[=\sum_{d=1}^{min(a,b)}\mu(d)\sum_{x=1}^a\sum_{y=1}^b[d|gcd(a,b)]\sum_{x|i}^a\sum_{y|j}^b 1\]

\[=\sum_{d=1}^{min(a,b)}\mu(d)\sum_{x=1}^a\sum_{y=1}^b[d|gcd(a,b)]\lfloor\frac{a}{x}\rfloor\lfloor\frac{b}{y}\rfloor\]

某一項太不好弄了，通過更改枚舉項拿掉

\[=\sum_{d=1}^{min(a,b)}\mu(d)\sum_{x=1}^{\lfloor\frac{a}ze8trgl8bvbq\rfloor}\sum_{y=1}^{\lfloor\frac{b}ze8trgl8bvbq\rfloor}\lfloor\frac{a}{dx}\rfloor\lfloor\frac{b}{dy}\rfloor\]

發現求和項也帶有下取整，預處理前綴和以后直接整除分塊就可以了。

---

Code:

#include <cstdio> #define ll long long const int N=5e4; int pri[N+10],mu[N+10],ispri[N+10],f[N+10],cnt,T,a,b; void init() {mu[1]=1;for(int i=2;i<=N;i++){if(!ispri[i]){pri[++cnt]=i;mu[i]=-1;}for(int j=1;j<=cnt&&pri[j]*i<=N;j++){ispri[i*pri[j]]=1;if(i%pri[j]==0) break;else mu[i*pri[j]]=-mu[i];}}for(int i=1;i<=N;i++){mu[i]+=mu[i-1];for(int l=1,r;l<=i;l=r+1){r=i/(i/l);f[i]+=i/l*(r-l+1);}} } int min(int x,int y){return x<y?x:y;} int main() {init();scanf("%d",&T);while(T--){scanf("%d%d",&a,&b);ll ans=0;for(int l=1,r;l<=min(a,b);l=r+1){r=min(a/(a/l),b/(b/l));ans+=1ll*(mu[r]-mu[l-1])*f[a/l]*f[b/l];}printf("%lld\n",ans);}return 0; }

---

2018.10.20

轉載于:https://www.cnblogs.com/butterflydew/p/9821948.html

總結

以上是生活随笔為你收集整理的洛谷 [SDOI2015]约数个数和 解题报告的全部內容，希望文章能夠幫你解決所遇到的問題。

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