[bzoj 2226] [Spoj 5971] LCMSum

求. T组数据. (1≤T≤3*10^5, 1≤n≤10^6)

令, 则

暂且暴力枚举n的因子. 由于数据范围较大, 最好预处理所有, 即[1,n]中与n互质的数之和. 再来推一发式子

于是可以递推计算.

暴力, TLE (显然会TLE, 不该心存侥幸). 换上筛法, 预处理变得可以接受了, 还是TLE. 通过打表, 发现满足这样一个式子 虽然不知道为什么, 还和欧拉函数的公式长得很像. 于是可以线性筛, 预处理变.

但还是决定先在求答案枚举n的因子那里优化: 同样可以用筛法. 时间复杂度变为, AC.

看了大爷们的题解, 呃......

来自Po姐的证明: 当, 由于, 所以与互质的数可以分成对, 每对之和等于. 具体分奇偶讨论: 首先, 由于, 和自己不互质. 若, 分成这长度相等的两段. 与有大于的公因子, 可以忽略. 若, 分成两段. 时特判, 发现符合上述公式.

来自iamxym的证明: 首先有这样两个式子: 莫比乌斯函数的定义式.

由等式反演得到.

#include <bits/stdc++.h>
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)

using namespace std;
typedef long long ll;
const int N = 1e6;
ll sum[N + 1], ans[N + 1];

void sieve()
{
	For (i, 1, N) {
		sum[i] += (ll)i*(i+1)/2;
		for (int j = 2; i*j <= N; ++j)
			sum[i*j] -= j*sum[i];
	}
	For (i, 1, N) {
		for (int j = 1; i*j <= N; ++j)
			ans[i*j] += sum[i];
		ans[i] *= i;
	}
}

int main()
{
	sieve();
	int T;
	scanf("%d", &T);
	while (T--) {
		int n;
		scanf("%d", &n);
		printf("%lld\n", ans[n]);
	}
	return 0;
}