3994: [SDOI2015]约数个数和
Time Limit: 20 Sec Memory Limit: 128 MB
Description
设d(x)为x的约数个数，给定N、M，求 
Input
输入文件包含多组测试数据。
第一行，一个整数T，表示测试数据的组数。
接下来的T行，每行两个整数N、M。
Output
T行，每行一个整数，表示你所求的答案。
Sample Input
2
7 4
5 6
7 4
5 6
Sample Output
110
121
121
HINT
1<=N, M<=50000
1<=T<=50000
结论题丧心病狂系列
其实看到这道题，我们发现最大的难点就是如何求\( d(nm) \)
暂且不说为什么，我们欣赏一下这个式子\[ d(nm)=\sum_{i \mid n}\sum_{j \mid m}\lbrack gcd(i,j)=1 \rbrack \]
其实我刚看到的时候是拒绝的，什么鬼啊？？？！！！
然后我们抛开这个式子，来分析一下某个质数\(p\)对答案的贡献
若\( n=n’ \times p^{k_{1}} \)， \( m=m’ \times p^{k_{2}} \)
则贡献为\( k_{1}+k_{2}+1 \)
然后我们观察开始给出的式子，发现一个素数对答案有贡献的还是\( (p^{k_{1}},1),(p^{k_{1}-1},1) \cdots (1,1) \cdots (1,p^{k_{2}-1}),(1,p^{k_{2}}) \)这\( k_{1}+k_{2}+1 \)个
所以我们证明了这个结论的成立。
接下来是莫比乌斯反演的正常推导
最终形式为\[ \sum_{g=1}^{N}\mu(g)\sum_{i=1}^{\lfloor \frac{N}{g} \rfloor}\sum_{j=1}^{\lfloor \frac{M}{g} \rfloor}\lfloor \frac{N}{ig} \rfloor\lfloor \frac{M}{jg} \rfloor \]
#include<bits/stdc++.h>
using namespace std;
template <class _T> inline void read(_T &_x) {
int _t; bool flag = false;
while ((_t = getchar()) != '-' && (_t < '' || _t > '')) ;
if (_t == '-') _t = getchar(), flag = true; _x = _t - '';
while ((_t = getchar()) >= '' && _t <= '') _x = _x * + _t - '';
if (flag) _x = -_x;
}
typedef long long LL;
const int maxn = ;
int f[maxn], mu[maxn], prime[maxn], pcnt;
bool vis[maxn];
inline int calc_f(int n) {
int ret = ;
for (int i = , j, t; i <= n; i = j + ) {
t = n / i, j = n / t;
ret += t * (j - i + );
}
return ret;
}
inline void init() {
mu[] = ;
for (int i = ; i < maxn; ++i) {
if (!vis[i]) {
prime[++pcnt] = i;
mu[i] = -;
}
for (int j = ; j <= pcnt && prime[j] * i < maxn; ++j) {
vis[prime[j] * i] = true;
if (i % prime[j] == ) {
mu[prime[j] * i] = ;
break;
}
mu[prime[j] * i] = -mu[i];
}
}
for (int i = ; i < maxn; ++i) {
mu[i] += mu[i - ];
f[i] = calc_f(i);
}
}
inline LL calc(int n, int m) {
if (n > m) swap(n, m);
LL ret = ;
for (int i = , j, t1, t2; i <= n; i = j + ) {
t1 = n / i, t2 = m / i, j = min(n / t1, m / t2);
ret += (mu[j] - mu[i - ]) * ((LL)f[t1] * f[t2]);
}
return ret;
}
int n, m;
int main() {
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
init();
int T; read(T);
while (T--) {
read(n), read(m);
printf("%lld\n", calc(n, m));
}
return ;
}