思考下最简真分数的概念，显然，其实就是找出 $1...n$ 所有最大公因数( $gcd$ )为 $1$ 的数，并且最小公因数为 $1$ 还对应着一个概念——互质！

所以其实这是一道欧拉函数的模板题。

欧拉函数，也被称为 $\phi$ 函数， $\phi(n)$ 也就是 $1..n$ 中与 $n$ 互质的数的数量。

例如 $\phi(1) = 1,\phi(4)=2$ 因为 $1$ 与自身互质，$4$ 与 $1,3$ 互质。

那么如何求欧拉函数呢？ 推导过程较为繁琐，可以观看视频学习。

算法协会培训视频 董晓算法

贴个线性求欧拉函数的模板：

const int N = 1e6 + 10;
vector<ll> phi, prime;
vector<int> st;

void init() {
    phi.resize(N);
    st.assign(N, 0);

    phi[1] = 1;
    for(int i = 2; i <= N; i ++) {
        if(!st[i]) {
            prime.push_back(i);
            phi[i] = i - 1;
        }

        for(auto p : prime) {
            if(p * i > N) {
                break;
            }

            st[i * p] = 1;
            if(i % p == 0) {
                phi[i * p] = phi[i] * p;
                break;
            }
            phi[i * p] = phi[i] * (p - 1);
        }
    }
}

注意，本题数据为 $1e7$ 数据较大，建议在主函数中加入如下代码，取消同步流。（时间限制已放宽至( $1500ms$ ）这个时间是造数据时的遗留问题，不用在意，这题数据还有神秘之处，如果用 $O2$ 优化，会比不用快四倍，内存小两倍，非常的神秘，也就是不用优化的话，很可能卡极限过不了，用优化就稳过。

ios::sync_with_stdio(0), cin.tie(0);
cout.tie(0);