AcWing 1358. 约数个数和(莫比乌斯反演经典、双上限整除分块)
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 50007;
typedef long long ll;
int n, m, t;
int primes[N];
ll res;
bool vis[N];
int mu[N];
int sum[N];
int cnt;
int H[N];
int g(int k, int x) {return k / (k / x);}
void init(int n)
{
mu[1] = 1;
for(int i = 2; i <= n; ++ i) {
if(vis[i] == 0) {
primes[ ++ cnt] = i;
mu[i] = -1;
}
for(int j = 1; j <= cnt && primes[j] * i <= n; ++ j) {
vis[i * primes[j]] = true;
if(i % primes[j] == 0) break;
mu[i * primes[j]] = -mu[i];
}
}
for(int i = 1; i <= n; ++ i) sum[i] = sum[i - 1] + mu[i];
for(int i = 1; i <= n; ++ i) {
for(int l = 1, r; l <= i; l = r + 1) {
r = min(i, g(i, l));
H[i] += (r - l + 1) * (i / l);
}
}
}
int main()
{
cin >> t;
init(N - 1);
while(t -- ) {
res = 0;
scanf("%d%d", &n, &m);
int k = min(n, m);
for(int l = 1, r; l <= k; l = r + 1) {
r = min(k, min(g(n, l), g(m, l)));
res += ((ll)sum[r] - sum[l - 1]) * H[n / l] * H[m / l];
}
printf("%lld\n", res);
}
return 0;
}
图片炸了\kk
orz
板书好好看,爱了爱了。
推柿子hh