Problem with SPOJ GCDEX

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	151

I was solving this problem. The formula for this problem can be founded here. I've stress tested my code, and found out that this is the smallest test case where my code failed (answer for n <= 225537 are all correct).

Input

Output

Expect

It is obvious that my output is wrong, since $$$answer(n) > answer(n-1)$$$. I have no idea why my code doesn't work.

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;

bool isprime[N];
vector<int> prime;
int mobius[N];
int phi[N];
int phi_pref[N];

void init() {
	fill(isprime, isprime + N, true);
	isprime[0] = isprime[1] = false;
	mobius[1] = 1;
	phi[1] = 1;
	for(int i = 2; i < N; ++i) {
		if(isprime[i]) {
			prime.push_back(i);
			mobius[i] = -1;
			phi[i] = i - 1;
		}
		for(auto& p : prime) {
			if(p * i >= N) {
				break;
			}
			isprime[p * i] = false;
			mobius[p * i] = mobius[p] * mobius[i];
			phi[p * i] = phi[p] * phi[i];
			if(i % p == 0) {
				mobius[p * i] = 0;
				phi[p * i] = phi[i] * p;
				break;
			}
		}
	}
	for(int i = 1; i < N; ++i) {
		phi_pref[i] = phi_pref[i - 1] + phi[i];
	}
}

int main(int argc, char* argv[]) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	init();
	int n;
	while(cin >> n && n) {
		long long ans = 0;
		for(int i = 1, j; i <= n; i = j) {
			int p = n / i;
			j = n / p + 1;
			ans += 1LL * p * (p - 1) / 2 * (phi_pref[j - 1] - phi_pref[i - 1]);
		}
		cout << ans << "\n";
	}
	return 0;
}

Polyn0mial's blog