Description
设d(x)为x的约数个数，给定N、M，求
[sum_{i=1}^{n}sum_{j=1}^md(i*j)
]
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
Solution
做这题首先要知道约数函数(d(x))的一个性质，不然完全做不下去
注：((x,y))表示(gcd(x,y))
[large
d(i*j)=sum_{x|i}sum_{y|j}[(x,y)=1]
]
证明的话..不难理解，但是写一遍很麻烦，所以直接看这篇文章吧...
https://blog.csdn.net/ab_ever/article/details/76737617
所以我们就可以开始推式子了
[large{
egin{aligned}
&sum_{i=1}^{n}sum_{j=1}^md(i*j)\
&=sum_{i=1}^{n}sum_{j=1}^msum_{x|i}sum_{y|j}[(x,y)=1]\
&=sum_{x=1}^{n}sum_{y=1}^{m}sum_{i=1}^{lfloorfrac{n}{x}
floor}sum_{j=1}^{lfloorfrac{m}{y}
floor}[(x,y)=1]\
&=sum_{x=1}^{n}sum_{y=1}^{m}lfloorfrac{n}{x}
floorlfloorfrac{m}{y}
floor[(x,y)=1]\
&=sum_{x=1}^{n}sum_{y=1}^{m}lfloorfrac{n}{x}
floorlfloorfrac{m}{y}
floorsum_{d|(x,y)}mu(d)\
&=sum_{d=1}^{n}sum_{x=1}^{lfloorfrac{n}{d}
floor}sum_{y=1}^{lfloorfrac{m}{d}
floor}lfloorfrac{n}{dx}
floorlfloorfrac{m}{dy}
floor*mu(d)\
&=sum_{d=1}^{n}mu(d)sum_{x=1}^{lfloorfrac{n}{d}
floor}sum_{y=1}^{lfloorfrac{m}{d}
floor}lfloorfrac{n}{dx}
floorlfloorfrac{m}{dy}
floor\
&=sum_{d=1}^{n}mu(d)sum_{x=1}^{lfloorfrac{n}{d}
floor}lfloorfrac{n}{dx}
floorsum_{y=1}^{lfloorfrac{m}{d}
floor}lfloorfrac{m}{dy}
floor\
end{aligned}\
设g(x)=sum_{i=1}^{n}{lfloorfrac{n}{i}
floor}\
则代入原式可得\
egin{aligned}
&sum_{d=1}^{n}mu(d)sum_{x=1}^{lfloorfrac{n}{d}
floor}lfloorfrac{n}{dx}
floorsum_{y=1}^{lfloorfrac{m}{d}
floor}lfloorfrac{m}{dy}
floor\
&=sum_{d=1}^{n}mu(d)*g(lfloorfrac{n}{d}
floor)*g(lfloorfrac{m}{d}
floor)
end{aligned}
}
]
那么处理g的函数值和莫比乌斯函数的函数值，就可以(O(Tsqrt{n}))处理了
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 50010
int p[N], vis[N], mu[N], sum[N];
int n, m, cnt;
ll ans = 0, g[N];
void init() {
mu[1] = 1;
for(int i = 2; i < N; ++i) {
if(!vis[i]) p[++cnt] = i, mu[i] = -1;
for(int j = 1; j <= cnt && i * p[j] < N; ++j) {
vis[i * p[j]] = 1;
if(i % p[j] == 0) break;
mu[i * p[j]] -= mu[i];
}
}
for(int i = 1; i < N; ++i) {
sum[i] = sum[i - 1] + mu[i];
for(int l = 1, r; l <= i; l = r + 1) {
r = i / (i / l);
g[i] += 1ll * (r - l + 1) * (i / l);
}
}
}
int main() {
init();
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
if(n > m) swap(n, m);
ans = 0;
for(int l = 1, r; l <= n; l = r + 1) {
r = min(n/(n/l), m/(m/l));
ans += 1ll * (sum[r] - sum[l - 1]) * g[n / l] * g[m / l];
// printf("%d %d %d
", (sum[r] - sum[l - 1]), g[n / l], g[m / l]);
}
printf("%lld
", ans);
}
return 0;
}