欧拉函数（线性筛）（超好Dong）

欧拉函数：对于一个正整数n，小于n且和n互质的正整数（包括1）的个数，记作φ(n) 。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6;

bool vis[maxn];

int prime[maxn];

int phi[maxn];    

void init()

{

    memset(vis, false, sizeof(vis));

    phi[1] = 1;

    int cnt = 0;

    for(int i = 2; i < maxn; i ++)

    {

        if(!vis[i]){

            prime[cnt++] = i;

            phi[i] = i - 1;

        }

        for(int j = 0; j < cnt && i * prime[j] < maxn; j ++)

        {

            vis[i * prime[j]] = true;

            if(i % prime[j] == 0){

                phi[i*prime[j]] = phi[i]*prime[j];

                break;

            }

            else{

                phi[i*prime[j]] = phi[i]*phi[prime[j]];   // phi[i]*(prime[j]-1);

            }

        }

    }

}

int main()

{

    int n;

    cin >> n;

    init();

    cout << phi[n]<<endl;

}

巴特西

欧拉函数（线性筛）（超好Dong）

欧拉函数：对于一个正整数n，小于n且和n互质的正整数（包括1）的个数，记作φ(n) 。

最新文章

热门文章