uva11426

可以化成簡單的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;
}