[BZOJ3994][SDOI2015]約數個數和

3994: [SDOI2015]約數個數和

Time Limit: 20 Sec??Memory Limit: 128 MB Submit: 1104??Solved: 762 [Submit][Status][Discuss]

Description

設d(x)為x的約數個數，給定N、M，求 ?

?

Input

輸入文件包含多組測試數據。

第一行，一個整數T，表示測試數據的組數。

接下來的T行，每行兩個整數N、M。

Output

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

Sample Input

2
7 4
5 6

Sample Output

110
121

HINT

?1<=N, M<=50000

1<=T<=50000

圖片好像掛了。。。那張圖是$\sum_{i=1}^n\sum_{j=1}^m d\left(ij\right)$

如果沒掛請忽視上面那排話

由對稱性，不妨設$n\le m$

有一個結論$d\left(xy\right)=\sum_{i\mid x}\sum_{j\mid y}\left[gcd\left(i,j\right)=1\right]$

這個證明的話可以考慮每個質因數的貢獻。。。意會一下

那么可以得到

$ans=\sum_{x=1}^n\sum_{y=1}^m\sum_{i\mid x}\sum_{j\mid y}\left[gcd\left(i,j\right)=1\right]$

$=\sum_{i=1}^n\sum_{j=1}^m\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor\left[gcd\left(i,j\right)=1\right]$

$=\sum_{i=1}^n\sum_{j=1}^m\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor\sum_{d\mid i,d\mid j}\mu\left(d\right)$

$=\sum_{d=1}^n\mu\left(d\right)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{n}{id}\rfloor\lfloor\frac{m}{id}\rfloor$

$=\sum_{d=1}^n\mu\left(d\right)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{\lfloor\frac{n}{d}\rfloor}{i}\rfloor\lfloor\frac{\lfloor\frac{m}{d}\rfloor}{i}\rfloor$

$=\sum_{d=1}^n\mu\left(d\right)\left(\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{\lfloor\frac{n}{d}\rfloor}{i}\rfloor\right)\left(\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{\lfloor\frac{m}{d}\rfloor}{i}\rfloor\right)$

令$g\left(n\right)=\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor$

那么$ans=\sum_{d=1}^n\mu\left(d\right)g\left(\lfloor\frac{n}{d}\rfloor\right)g\left(\lfloor\frac{m}{d}\rfloor\right)$

而$g$可以通過枚舉每個分子然后不停的往倍數上加$1$，然后掃一遍前綴和求出，我為了用Latex碼數學公式現在已經頭昏眼花神志不清，如果你覺得我已經開始胡言亂語了導致你沒看懂那就看看代碼吧

預處理時間復雜度為$O\left(nlnn\right)$

似乎神犇們都是$O\left(n\right)$預處理？？？我還是太菜了哎

每次詢問的話分塊求，總時間復雜度$O\left(T\sqrt{n}\right)$

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 50000 + 10;
bool mark[maxn] = {false};
int mu[maxn], g[maxn] = {0}, sum[maxn];
int pri[maxn], prn = 0;
void shai(){mu[1] = 1;for(int i = 2; i < maxn; i++){if(!mark[i]){mu[i] = -1;pri[++prn] = i;}for(int j = 1; j <= prn && pri[j] * i < maxn; j++){mark[i * pri[j]] = true;if(i % pri[j] == 0){mu[i * pri[j]] = 0;break;}else mu[i * pri[j]] = -mu[i];}}for(int i = 1; i < maxn; i++)for(int j = i; j < maxn; j += i)g[j]++;sum[0] = g[0] = 0;for(int i = 1; i < maxn; i++){sum[i] = mu[i] + sum[i - 1];g[i] += g[i - 1];}
}
int main(){shai();int T, n, m;ll ans;scanf("%d", &T);while(T--){scanf("%d %d", &n, &m);if(n > m) swap(n, m);ans = 0;for(int p, i = 1; i <= n; i = p + 1){p = min(n / (n / i), m / (m / i));ans += (ll) (sum[p] - sum[i - 1]) * g[n / p] * g[m / p];}printf("%lld\n", ans);}return 0;
}

?