Rockdu's Blog

题目描述

for i=1 to n

for j=1 to n

 sum+=gcd(i,j)

给出n求sum. gcd(x,y)表示x,y的最大公约数.

输入输出格式

输入格式：

n

输出格式：

sum

输入输出样例

2

5

说明

数据范围 30% n<=3000 60% 7000<=n<=7100 100% n<=100000

题目十分奇特，我们知道1e6的数据n^2 log n 卡不死你也能卡爆你。我们需要将复杂度控制在O(n log n)以内。我们这样想，首先这些GCD可以被重新分类：GCD值为同一个数倍数的为一类，有什么好处呢？我们发现对于每一个i，那么gcd为i的倍数的个数就是(n/i)^2 (/表示整除)，那么这一类的和就是(n/i)^2 * i，这样我们只需要进行容斥统计每一个i就可以了。想到了倍数，那么我们就可以考虑这样一个问题：类似莫比乌斯函数，我们是不是也可以用类似的方法推断出在一定前缀之内，每一个i类的数应该被计算多少次呢？于是我们可以先用一层递推推出每一个i类数对应该计算多少次。那么最后的答案就变成了sum = sig(f[i] * (n/i) ^ 2)。就可以O(n log n)预处理O(n)查询了。但是其实我们能更优，做到根号n的复杂度。具体看代码：

#include<cstdio>
using namespace std;
const int maxn = 1e5 + 5;
long long f[maxn];
int n;

int pre(int n) {
	for(register int i = 1; i <= n; ++i){
		for(register int j = i * 2; j <= n; j += i)
			f[j] += i - f[i];
		f[i] = i - f[i];
		f[i] += f[i - 1];
	}
}

int main() {
	scanf("%d", &n);
	pre(n);
	int dis = 1;
	long long sig = 0;
	for(register int i = 1; i <= n; i = dis + 1) {
		dis = (n / (n / i));
		sig += (f[dis] - f[i - 1]) * (n / i) * (n / i);
	}
	printf("%lld\n", sig);
	return 0;
}