[NOI 2010] 能量采集

求平面直角坐标系中横坐标在[1,n], 纵坐标在[1,m]的所有整点与原点连线上的整点数目 (不含端点) 乘2加1之和. (1≤n,m≤100000) 原点与(x0,y0)所连的线段上有多少个整点 (不含端点)? 这些点满足方程 先将约分为. 假设是整数, 那么是整数当且仅当, 定义域内这样的点有个.

所以, 我们求的实际上是. 下面考虑怎么求.

如果, 可以转化为求. 枚举, 借助欧拉函数, 容易在的时间复杂度内求解. 但这里m, n并没有什么特殊限制. 试图用正方形拼矩形, 失败.

看了题解中的一连串 "显然" 好受伤......

对于每个, 求有多少对满足. 设答案为, 考虑减法.

首先, 必须是的公因子, 满足这一限制的有个. 这些数对的最大公约数一定是的倍数. 只要1倍的, 所以把2, 3, ...倍的减掉即可. 由于一对数的最大公约数是唯一的, 所以不会重复. 故:

倒序枚举, 递推即可.

果然NOI的题整体质量高.

#include <bits/stdc++.h>
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)

using namespace std;
typedef long long ll;
const int N = 1e5;
ll f[N + 1];

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