Problem with SPOJ GCDEX

#	User	Rating
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

#	User	Contrib.
1	maomao90	174
2	awoo	164
2	adamant	164
4	TheScrasse	159
4	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

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