（每日一题）P1447 [NOI2010] 能量采集（莫反套路 + 欧拉反演 / 容斥原理）

整理的算法模板合集： ACM模板

点我看算法全家桶系列！！！

实际上是一个全新的精炼模板整合计划

---

每日一题（莫反 / 多项式 / 母函数 / 群论） 2021.4.19 莫反

Problem

Solution

A. 莫比乌斯反演 + 欧拉反演

先简单解释一下本题解题第一步用到的显然的结论。

数轴上任意一点 $(x_1,y_1)$ 到原点之间线段上的经过的点 $(x_2,y_2)$ ，$\gcd (x_2,y_2)$ 一定是 $\gcd (x_1,y_1)$ 的因子。例如仪仗队那道题，从原点出发能看到的点一定都是 $\gcd (x,y)=1$ 的点。从原点到 $(x_1,y_1)$ 所以经过的点的个数就是 $\gcd (x_1,y_1)-1$（去掉自身）（ $(2,4)$ 会有因子 $(1,2)$ ）

证明来源：

Code

简单的代码：

Time

$O(n+\sqrt{n})$

// Problem: P1447 [NOI2010] 能量采集
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1447
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 500007;

int primes[N], cnt, phi[N];
int n, m;
bool vis[N];
int sum[N];

void init(int n)
{
   
	phi[1] = 1; 
	for(int i = 2; i <= n; ++ i) {
   
		if(vis[i] == 0) {
   
			primes[ ++ cnt] = i;
			phi[i] = i - 1;
		}
		for(int j = 1; j <= cnt && i * primes[j] <= n; ++ j) {
   
			vis[i * primes[j]] = true;
			if(i % primes[j] == 0) {
   
				phi[i * primes[j]] = phi[i] * primes[j];
				break;
			} 
			phi[i * primes[j]] = phi[i] * phi[primes[j]];
		}
	}
	for(int i = 1; i <= n; ++ i) {
   
		sum[i] = sum[i - 1] + phi[i]; 	
	}
}

void solve()
{
   
	int res = 0;
	for(int l = 1, r; l <= n; l = r + 1) {
   
		r = min(n / (n / l), m / (m / l));
		res +=  (n / l) * (m / l) * (sum[r] - sum[l - 1]);//(sum[r] - sum[l - 1])已经是区间长度了
	}
	res = 2 * res - n * m;
	printf("%lld\n", res);
}

signed main()
{
   
	init(N - 7);
	scanf("%lld%lld", &n, &m);
	if(n > m) swap(n, m);
	solve();
	return 0;
}

B. 容斥原理

时间复杂度 $O(nlogn)$

%%%

// Problem: P1447 [NOI2010] 能量采集
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1447
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 500007;

int n, m;
int f[N];

signed main()
{
   
	scanf("%lld%lld", &n, &m);
	if(n > m) swap(n, m);
	int ans = 0;
	for(int i = n; i; -- i) {
   
		f[i] = (n / i) * (m / i);
		for(int j = i << 1; j <= n; j += i) 
			f[i] -= f[j];
		ans += (2 * i - 1) * f[i];
	}
	printf("%lld\n", ans);
	return 0;
}

转载：https://blog.csdn.net/weixin_45697774/article/details/115841169