P3327 [SDOI2015]约数个数和

题目描述

设d(x)为x的约数个数，给定N、M，求 $\sum^N_{i=1}\sum^M_{j=1}d(ij)$

输入输出格式

输入格式：
输入文件包含多组测试数据。第一行，一个整数T，表示测试数据的组数。接下来的T行，每行两个整数N、M。

输出格式：
T行，每行一个整数，表示你所求的答案。

输入输出样例

输入样例#1： 复制
2
7 4
5 6
输出样例#1： 复制
110
121
说明

1<=N, M<=50000

1<=T<=50000

## 思路:
这道题有一个非常牛逼的结论：
$$d(n\cdot m)=\sum_{i|n}\sum_{j|m}[gcd(i,j)=1]$$
为什么呢？我们把i看做枚举n的质因数的子集，j看做枚举m的质因数的子集的补集。首先，这样不会有多算的部分，因为保证$gcd(i,j)=1$就是保证了i，j枚举的集合不相交。其次，这样一定会枚举全，因为我们枚举了所有不相交子集。
<space>
那么，让我们开始愉快的数学之旅吧！
原式：
$$\sum^N_{i=1}\sum^M_{j=1}\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]$$
$$\sum^N_{x=1}\lfloor\frac{n}{x}\rfloor\sum^M_{y=1}\lfloor\frac{m}{y}\rfloor[gcd(x,y)=1]$$
$$\sum^N_{x=1}\lfloor\frac{n}{x}\rfloor\sum^M_{y=1}\lfloor\frac{m}{y}\rfloor\sum_{k|x, k|y}\mu(k)$$
$$\sum^n_{k=1}\mu(k)\sum^{\frac{n}{k}}_{i=1}\lfloor\frac{n}{ki}\rfloor\sum^{\frac{m}{k}}_{j=1}\lfloor\frac{m}{kj}\rfloor$$
注意到题目范围是5e4，那么我们用$O(n\sqrt{n})$预处理后面的函数:$F(x) = \sum^{x}_{j=1}\lfloor\frac{x}{j}\rfloor$就可以了。

```
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn = 1e5 + 5;
int pri[maxn], mu[maxn], s[maxn], vis[maxn], f[maxn], t, a, b, mn;
LL ans;

void Pri(int n) {
    vis[1] = mu[1] = 1;
    for(register int i = 2; i <= n; ++i) {
        if(!vis[i]) mu[i] = -1, pri[++pri[0]] = i;
        for(register int j = 1; j <= pri[0] && i * pri[j] <= n; ++j) {
            vis[i * pri[j]] = 1;
            mu[i * pri[j]] = -mu[i];
            if(i % pri[j] == 0) {
                mu[i * pri[j]] = 0;
                break;
            }
        }
    }
    for(register int i = 1; i <= n; ++i)
        s[i] = s[i - 1] + mu[i];
}

void GetF(int n) {
    for(register int i = 1; i <= 50000; ++i) {
        for(register int l = 1, r = 1; l <= i; l = r + 1) {
            r = i / (i / l);
            f[i] += (i / l) * (r - l + 1);
        }
    }
}

int main() {
    Pri(50000), GetF(50000);
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &a, &b);
        mn = min(a, b), ans = 0;
        for(register int l = 1, r = 1; l <= mn; l = r + 1) {
            r = min(a / (a / l), b / (b / l));
            ans += 1ll * (s[r] - s[l - 1]) * f[a / l] * f[b / l];
        }
        printf("%lld\n", ans);
    }
    return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链