「POJ-3090」Visible Lattice Points-欧拉函数

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <iostream>
const int MAXN = 1000;
int phi[MAXN + 10], prime[MAXN + 10], tot, f[MAXN + 10];
bool vis[MAXN + 10];
inline void getPhi() {
    phi[1] = 1;
    for (register int i = 2; i <= MAXN; i++) {
        if (!vis[i]) prime[++tot] = i, phi[i] = i - 1;
        for (register int j = 1; j <= tot; j++) {
            if (i * prime[j] > MAXN)  break;
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}
int main() {
    getPhi();
    int c, n;
    scanf("%d", &c);
    f[1] = 1;
    for (register int i = 2; i <= MAXN; i++) f[i] = f[i - 1] + phi[i];
    for (register int i = 1; i <= c; i++) scanf("%d", &n), printf("%d %d %d\n", i, n, f[n] << 1 | 1);
    return 0;
}