Rockdu's Blog

这是蓝书上一道很经典的数论题，位于P124页，只不过题意有一些细微偏差，但是不影响本题结论的正确性，做法可以看：洛谷P2398。我们只需要进行一次预处理，下底分块，保留SQRT(n)的查询就行了。虽然时间上Vjudge垫底，但是毕竟我弱啊……，下面是一段代码。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 4e6 + 5;
long long f[maxn];
int n[105], cnt, mx;

int prewri(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[cnt]), mx = max(n[cnt], mx);
	while(n[cnt]) scanf("%d", &n[++cnt]), mx = max(mx, n[cnt]);
	prewri(mx);
	for(register int j = 0; j < cnt; ++j) {
		int dis = 1;
		long long sig = 0;
		for(register int i = 1; i <= n[j]; i = dis + 1) {
			dis = (n[j] / (n[j] / i));
			sig += (f[dis] - f[i - 1]) * (n[j] / i) * (n[j] / i - 1) / 2;
		}
		printf("%lld\n", sig);
	}
	return 0;
}