记录编号	600739	评测结果	AAAAAAAAAA
题目名称	[河南省队2012] 最大公约数和	最终得分	100
用户昵称	对立猫猫对立	是否通过	通过
代码语言	C++	运行时间	0.030 s
提交时间	2025-05-12 21:43:15	内存使用	3.68 MiB

#include <bits/stdc++.h>
#define int long long
#define Tairisu return 0;
using namespace std;
int N, out = 0;
int phi(int n) {
	int ans = n;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			ans = ans / i * (i - 1);
			while (n % i == 0) n /= i;
		}
	}
	if (n > 1) ans = ans / n * (n - 1);
	return ans;
}
signed main() {
	freopen("gcdsum.in", "r", stdin);
	freopen("gcdsum.out", "w", stdout);
	cin >> N;
	for (int i = 1; i * i <= N; i++) {
		if(N % i == 0)
		{
			if (i * i == N) out += phi(i) * i;
			else out += phi(i) * (N / i) + phi(N / i) * i;
		}
	}
	cout << out << endl;
	Tairisu
}