AcWing 874 筛法求欧拉函数 题解

    #include<iostream>
    
    using namespace std;
    
    typedef long long ll;
    
    const int N = 1e6 + 10;
    
    int prime[N], cnt;
    int oulr[N];
    int n;
    ll ans;
    bool st[N];
    
    ll get_oulr(int x){
    	oulr[1] = 1;
    	for(int i = 2; i <= x; i ++ ){
    		if(!st[i]){//当i为质数时，i的欧拉函数值为i-1
    			st[i] = true;
    			prime[cnt ++ ] = i;
    			oulr[i] = i - 1;
    		}
    		for(int j = 0; j < cnt && prime[j] * i <= x; j ++ ){