洛谷 2257

莫比乌斯反演半模板题

很容易可以得到

[Ans = sumlimits_{p in prime} sumlimits_{d = 1}^{min (leftlfloorfrac{a}{p} ight floor, leftlfloorfrac{b}{p} ight floor)} mu(d) leftlfloorfrac{a}{pd} ight floorleftlfloorfrac{b}{pd} ight floor ]

那么现在由于想要进行整除分块，所以希望将 (sum) 内部的向下取整部分移到外部，故令 (T = dp) ，则有

[egin{aligned} Ans &= sumlimits_{T = 1}^{min (a, b)} sumlimits_{p | T, p in prime} mu(leftlfloorfrac{T}{p} ight floor) leftlfloorfrac{a}{T} ight floorleftlfloorfrac{b}{T} ight floor \ &= sumlimits_{T = 1}^{min (a, b)} leftlfloorfrac{a}{T} ight floorleftlfloorfrac{b}{T} ight floor left( sumlimits_{p | T, p in prime} mu(leftlfloorfrac{T}{p} ight floor) ight) end{aligned} ]

那么用筛法预处理一下 (mu) 的那一部分就可以直接整除分块了

代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long LL;

const int MAXN = 1e07 + 10;

int prime[MAXN];
int vis[MAXN]= {0};
int pcnt = 0;
int mu[MAXN]= {0};
LL tsum[MAXN]= {0}, sum[MAXN]= {0};
const int MAX = 1e07;
void prime_Acqu () {
	mu[1] = 1;
	for (int i = 2; i <= MAX; i ++) {
		if (! vis[i]) {
			prime[++ pcnt] = i;
			mu[i] = - 1;
		}
		for (int j = 1; j <= pcnt && i * prime[j] <= MAX; j ++) {
			vis[i * prime[j]] = 1;
			if (! (i % prime[j]))
				break;
			mu[i * prime[j]] = - mu[i];
		}
	}
	for (int j = 1; j <= pcnt; j ++)
		for (int i = 1; i * prime[j] <= MAX; i ++)
			tsum[i * prime[j]] += mu[i];
	for (int i = 1; i <= MAX; i ++)
		sum[i] = sum[i - 1] + tsum[i];
}

LL Calc (int a, int b) {
	LL ans = 0;
	int limit = min (a, b);
	for (int l = 1, r; l <= limit; l = r + 1) {
		r = min (a / (a / l), b / (b / l));
		ans += (sum[r] - sum[l - 1]) * (a / l) * (b / l);
	}
	return ans;
}

int T;

int getnum () {
	int num = 0;
	char ch = getchar ();

	while (! isdigit (ch))
		ch = getchar ();
	while (isdigit (ch))
		num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();

	return num;
}

int main () {
	prime_Acqu ();
	T = getnum ();
	for (int Case = 1; Case <= T; Case ++) {
		int a = getnum (), b = getnum ();
		LL ans = Calc (a, b);
		printf ("%lld
", ans);
	}

	return 0;
}

/*
2
10 10
100 100
*/