luogu1447 [NOI2010]能量采集

考虑暴力，答案显然是 \(\sum_{i=1}^n\sum_{j=1}^m(2(\gcd(i,j)-1)+1)=\sum_{i=1}^n\sum_{j=1}^m(2\gcd(i,j)-1)\)。

考虑优化，设 \(f(i)\) 是 \(\gcd(x,y) = i\) 的点的个数，则 \(\sum_{i=1}^{\min(n,m)}f(i)(2i-1)\) 即为答案。

考虑优化 \(f(i)\) 的计算，我们可以先算出 \(i\) 作为公约数的个数 \(\left \lfloor \frac{n}{i} \right \rfloor \left \lfloor \frac{m}{i} \right \rfloor\)，然后减去许多个 \(f(j)\) ，其中 \(i < j \leq \min(n,m)\) 并且 \(i|j\)。

#include <iostream>

using namespace std;

typedef long long ll;

int n, m;

ll f[100005], ans;

int main(){

	cin>>n>>m;

	if(n>m)	swap(n, m);

	for(int i=n; i; i--){

		f[i] = (ll)(n/i) * (ll)(m/i);

		for(int j=i+i; j<=n; j+=i)

			f[i] -= f[j];

		ans += f[i] * (2 * i - 1);

	}

	cout<<ans<<endl;

	return 0;

}

巴特西

luogu1447 [NOI2010]能量采集

最新文章

热门文章