luogu2398 SUM GCD

题目大意：求sum i(1->n) (sum j(1->n) (gcd(i,j)))。

对于每对(i,j)都来一次gcd很慢，但是我们知道，一个约数i在1~n范围内是n/i个数的约数。gcd也是个约数，如果能利用到这一点，不就可以同时处理很多对(i,j)了吗？

我们看看最大公约数等于i的数对(x,y)个数f[i]是多少，再让f[i]*(2*i-1)就是这个最大公因数对答案ans做出的贡献。

f[i]=公约数中含有i的个数-sum j(i->min(m,n)/i) (f[i*j])。容斥原理，如果i*j是某个数对的最大公因数，则i就不是它的最大公因数。把这样的点都抠掉，剩下的就都是关于最大公因数是i的了。

公约数含有i的个数=m/i*n/i。数对(x,y)的公约数中含有i当且仅当i既是x的约数又是y的约数。先选择约数中含有i的x，其有m/i个。这时再选择y，其有n/i个。根据乘法原理，因为是依次选择，所以两个式子相乘。

#include <cstdio>

using namespace std;

#define ll long long

const int MAX_N = 100010;

ll Proceed(ll n)

{

	ll ans = 0;

	static ll f[MAX_N];

	for (int i = n; i >= 1; i--)

	{

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

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

			f[i] -= f[i*j];

		ans += i*f[i];

	}

	return ans;

}

int main()

{

#ifdef _DEBUG

	freopen("c:\\noi\\source\\input.txt", "r", stdin);

#endif

	ll n;

	scanf("%lld", &n);

	printf("%lld\n", Proceed(n));

	return 0;

}

巴特西

luogu2398 SUM GCD

最新文章

热门文章