luoguP1447 [NOI2010]能量采集

https://www.luogu.org/record/22874213

题目大意:给定n和m,求Σ(1<=i<=n)Σ(1<=j<=m)GCD(i,j)* 2-1

i和j的限制不同,传统的线性筛法失效了,这里我们考虑容斥原理

设：f(x) = ΣΣ[ gcd(i,j)==x ]

那么答案即为 Σf(x)* x, x:1->n //规定n<m, 即gcd(n,m)<=n

g(x) = Σ[ x | gcd(i,j) ] = n/x * m/x = f(x) + f(2x) + ... + f(n/x * x)

i: x, 2x...n/x * x, j: x, 2x...m/x * x。所以gcd(i,j)为x倍数的有 (n/x) * (m/x)

移项一下，用原先预处理好的g[]算f[], f(x) = g(x) - f(2x) - f(3x) - ... - f(n/x* x)

倒过来算f(x)，那么f(2x)...f(n/x * x)就都算好了

#include<cstdio>

#include<iostream>

using namespace std;

#define MAX 100000+999

#define ll long long

ll f[MAX];

int n,m;

int main() {

	scanf("%d%d",&n,&m);

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

	for(int i = 1; i <= n; i++) f[i] = (ll)(n/i) * (m/i);// 注意加括号！！！ //注意变longlong

	for(int i = n; i >= 1; i--) {//求f[i]

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

			f[i] -= f[j];

		}

	}

	ll ans = 0;

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

		ans += f[i]*i;

//	for(int i = 1; i <= n; i++) printf("%d\n",f[i]);

	printf("%lld",(ans<<1) - (ll)n*m);//把Σ变一下

}

巴特西

luoguP1447 [NOI2010]能量采集

最新文章

热门文章