详见代码:
#include#include #include #include using namespace std;// 给定一个数N,求1-N的所有数与这个数的gcd之和// 观察gcd函数,我们可以得知那些与N互质的数的gcd一定为1,也就是欧拉函数 // 那么那些不互质的数有gcd(x, N) = d // 也就是gcd(x/d, N/d) = 1,所以我们继续求N/d的欧拉函数就可以了 int eular(int x) { // 直接对某一个数进行素因子分解求解 int ret = 1; for (int i = 2; i <= (int)sqrt(double(x)); ++i) { if (x % i == 0) { ret *= i-1; x /= i; while (x % i == 0) { ret *= i; x /= i; } } } if (x != 1) { ret *= x-1; } return ret;}int main() { int N; long long ret; while(scanf("%d", &N) == 1) { ret = 1LL * eular(N) + N; // 统计出所有互质的数以及这个数本身 for (int i = 2; i <= (int)sqrt(double(N)); ++i) { // 枚举出所有的因子 if (N % i == 0) { // 枚举所有的因子 if (i * i == N) { ret += 1LL * eular(i) * i; } else { ret += 1LL * eular(i) * (N/i); ret += 1LL * eular(N/i) * i; } } } printf("%lld\n", ret); } return 0;}