1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstring>
#include <iostream>
using namespace std;
#include <vector>
#define ll long long
ll const Maxn = 5000005;
bool Isprime [Maxn];
ll  phi[Maxn];
vector<ll>  primelist;
void init(){
    memset(Isprime,0,sizeof(Isprime));
    memset(phi,0,sizeof(phi));
    int primecount = 0;
    for(int i=2;i<Maxn;i++){
        if(Isprime[i]==0){
            primelist.push_back(i);
            primecount++;
            phi[i]=i-1;
        }
        for(int j=0;j<primelist.size();j++){
            if(i*primelist[j]>=Maxn)  break;
            Isprime[i*primelist[j]] = 1;
            if(i%primelist[j]==0){
                // primeList[j]是i的约数，φ(n*p) = φ(n) * p
                phi[ i * primelist[j] ] = phi[i] * primelist[j];
                break;
            }
            else{
                phi[ i * primelist[j] ] = phi[i] * (primelist[j] - 1);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX