Codeforces Round #818 (Div. 2) E 补题

原题链接

发现枚举\(gcd(a,b)\)的值时间复杂度最优，因为\(a+b=k*gcd(a,b) (k=2,3,4...)\)，这样的话总的枚举次数就是调和级数，所以外层枚举的复杂度为\(O(nlogn)\)，问题转化为怎么快速得到同时满足\(gcd(a,b)=i\)和\(a+b=k*i\)这两个条件的\((a,b)\)数量
有一个引理，设\(a+b=c\)，那么\(gcd(a,b)=1\)的充要条件是\(gcd(a,c)=1\)这篇题解有证明
那么数对\((a,b)\)满足条件的充要条件就是\(gcd(a/i,k*i/i)=1\)，就是求小于\(k\)并且与\(k\)互质的正整数个数，即为\(k\)的欧拉函数
总的时间复杂度\(O(nlognlogn)\)

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

#define fr first
#define se second
#define et0 exit(0);
#define rep(i, a, b) for(int i = (int)(a); i <= (int)(b); i ++)
#define rrep(i, a, b) for(int i = (int)(a); i >= (int)(b); i --)
#define IO ios::sync_with_stdio(false),cin.tie(0);

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef unsigned long long ULL;

const int INF = 0X3f3f3f3f, N = 1e5 + 10, MOD = 1e9 + 7;
const double eps = 1e-7, pi = acos(-1);

LL phi[N];
int primes[N], st[N];

LL get_eulers(int n) {
	int cnt = 0;
	LL res = 0;
	phi[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!st[i]) {
			primes[cnt++] = i;
			phi[i] = i - 1;
		}
		for (int j = 0; primes[j] * i <= n; j++) {
			st[primes[j] * i] = 1;
			if (i % primes[j] == 0) {
				phi[i * primes[j]] = phi[i] * primes[j];
				break;
			} else phi[i * primes[j]] = phi[i] * (primes[j] - 1);
		}
	}
	for (int i = 1; i <= n; i++) res += phi[i];
	return res;
}

int gcd(int x, int y) {
	return y == 0 ? x : gcd(y, x % y); 
}

inline int add(int x, int y) {
	return (LL) x + y > MOD ? x + y - MOD : x + y;
}

int lcm(int x, int y) {
	return (LL)x / gcd(x, y) * y % MOD;
}

void work() {
	int n;
	cin >> n;
	int res = 0;
	rep (i, 1, n) {
		for (int j = 2 * i; j < n; j += i) {
			res = add(res, (LL)phi[j / i] * lcm(n - j, i) % MOD);
		}
	}
	cout << res << endl;
}

signed main() {
	IO
	get_eulers(N);

	int test = 1;

	while (test--) {
		work();
	}

	return 0;
}