可以化成简单的s[n] = s[n - 1] + f[n]
关键在于求f[n] = gcd(1, n) + gcd(2, n) + ... + gcd(n - 1, n)
直接裸求的话肯定会超时。可以把上面的和按和n的约数来分类。
约数为1,2,3...
那么结果就为sums{i * g(i, n)};
g(i, n)表示和n约数为i的数的个数、相当于求gcd(x / i, n /i) == 1的数的个数,就是phi[n / i];
但是如果顺序枚举的话时间会很慢,不如反过来,求约数开始枚举。
约数为1,约数为2...
求出f[n]即可。
#include <cstdio>
#include <string.h>
#include <iostream>
const int MAX_NUMBER = 4000000;
long long value[MAX_NUMBER + 2], phi[MAX_NUMBER + 2], f[MAX_NUMBER];
void getPhiTable() {
memset(phi, 0, sizeof(phi));
phi[1] = 1;
for (int i = 2; i <= MAX_NUMBER; i++) {
if (!phi[i]) {
for (int j = i; j <= MAX_NUMBER; j += i) {
if (!phi[j]) {
phi[j] = j;
}
phi[j] = phi[j] / i * (i - 1);
}
}
}
}
void getF() {
for (int i = 1; i <= MAX_NUMBER; i++) {
for (int j = i * 2; j <= MAX_NUMBER; j += i) {
f[j] += i * phi[j / i];
}
}
}
int number;
int main() {
getPhiTable();
getF();
value[2] = 1;
for (int i = 3; i <= MAX_NUMBER; i++) {
value[i] = value[i - 1] + f[i];
}
while (scanf("%d", &number) != EOF) {
if (!number) {
break;
}
std::cout << value[number] << std::endl;
}
return 0;
}