题解 P1447 【[NOI2010]能量采集】

查看原题请戳这里

一开始以为需要用线性筛（当然我不会），后来才知道原来容斥一下就可以通过这道题目……

首先，有一个奇怪的结论：横纵坐标gcd为$k$的点前面共有$k-1$个（它们的gcd分别为$1,2…k-1$）。

我们可以发现，对于一个$n\times m$的图，横纵坐标的公因数含有$k$的点共有$((n/k)\times(m/k))$个，即共有$n/k$个横坐标为$k$的倍数，有$m/k$个纵坐标为$k$的倍数，那么点数为$((n/k)\times(m/k))$个。

于是我们就可以快速预处理出$x$坐标和$y$坐标公因数为$k$的点。

然后我们考虑容斥。

比如，我们要求横坐标和纵坐标gcd为$2$的点，那么我们可以用公因数包含$2$的点减去gcd为$4$的点在减去gcd为$8$的点，再减去gcd为$16$的点，再减去……

好吧，这个容斥貌似被魔改过……

但是容斥的复杂度很大怎么办？

我们可以从大数向小数枚举，比如我们枚举到$4$时，我们就直接把其中gcd为$4$的倍数（除了$4$）的点的数量直接删去就好了。

code：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define re register

using namespace std;

int read()
{
    register int x = 0,f = 1;register char ch;
    ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
    while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
    return x * f;
}

long long n,m,cnt,ans,a[1000005];

int main()
{
	n = read(); m = read();
	for(int i = 1; i <= n; i++) a[i] = (n / i) * (m / i);
	for(int i = n; i >= 1; i--)
	{
		for(int j = 2; j <= n / i; j++) a[i] = a[i] - a[i * j];
		ans = ans + a[i] * (i * 2 - 1);
	}
	cout << ans << endl;
    return 0;
}