欧拉函数 Euler Function

声明：本人与zhangjianhao0518共创

打错了，把当成吧

前铺

一.欧拉筛（线性筛）

此方法广泛用于素数筛选，尤其是数据大时,时间复杂度为O（N）。

const int N = 1e7+10;
int cnt = 0,prime[N];
bool vis[int(1e8+5)];
void ola(){
    vis[0]=vis[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i]){
            prime[++cnt] = i;
        }
        for(int j=1;j<=cnt&&1ll*i*prime[j]<=n;j++){
            vis[prime[j]*i] = 1;
            if(i%prime[j]==0) break;
        }
    }
}
//prime用于存储每个素数

 二.积性函数

（i）若有,为积性函数。

（ii）, 为积性函数，叫欧拉函数

  (iii)  莫比乌斯函数 (p is a prime)
  

(iv)求欧拉函数 (p is a prime)

                      其中 m = 

            性质  1.   p|n且p^2|n ,则   

（V）欧拉定理 ：若a与m 互质

                                a^(m)(mod m)

题目

T1 求欧拉函数（模板题）

时间限制：1秒        内存限制：128M

题目描述

输入𝑛，请输出𝜙(𝑛)的值。

输入描述

多组输入。每组输入一个整数𝑛(𝑛≤10^9)。当输入的𝑛=0时结束。

输出描述

对于每组输入，输出一个整数表示答案。

样例输入

1. 7
2. 12
3. 0

样例输出

1. 6
2. 4

#include<iostream>
#include<cmath>
using namespace std;
const int N = 1e7+10;
int n;
int get_phi(int n){
    int m=int(sqrt(n+0.5));
    int ans = n;
    for(int i=2;i<=m;i++){
        if(n%i==0) {
            ans = ans/i*(i-1);
            while(n%i==0) n/=i;
        }
    }
    if(n>1) ans= ans/n*(n-1);
    return ans;
}
int main(){
    while(cin>>n){
        if(n==0){
            break;
        }
        cout<<get_phi(n)<<"\n";
    }
    return 0;
}

 T2莫比乌斯与欧拉（模板题）

题目描述

给定𝑛,𝑇n,T，每次在区间[1,𝑛]中选一个数𝑥，请输出𝜇(𝑥))或𝜙(𝑥)

输入描述

第一行两个正整数𝑛,𝑇(1≤𝑛,𝑇≤10^6)

接下来𝑇T行，每行两个整数𝑜𝑝𝑡,𝑥(1≤𝑜𝑝𝑡≤2,1≤𝑥≤𝑛)，如果𝑜𝑝𝑡=1opt=1，请输出𝜇(𝑥))，否则请输出𝜙(𝑥)

输出描述

如题

样例输入

1. 10 5
2. 1 4
3. 2 7
4. 1 7
5. 2 3
6. 2 9

样例输出

1. 0
2. 6
3. -1
4. 2
5. 6

#include<iostream>
#include<cmath>
using namespace std;
const int N = 1e6+10;
int n,t,cnt;
int vis[N],prime[N],mu[N],phi[N];
void sieve(){
    vis[1]=mu[1]=phi[1]=1;
    for(int i=2;i<N;i++){
        if(!vis[i]){
            prime[++cnt]=i;
            mu[i]=-1;
            phi[i]=i-1;
        }
    
        for(int j=1;j<=cnt&&1ll*i*prime[j]<N;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                mu[i*prime[j]]=0;
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            mu[i*prime[j]]=-mu[i];
            phi[i*prime[j]]=phi[i]*phi[prime[j]];
        }
    }
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>t;
    sieve();
    while(t--){
        int opt,x;
        cin>>opt>>x;
        if(opt==1){
            cout<<mu[x]<<"\n";
        }else{
            cout<<phi[x]<<"\n";
        }
    }
    return 0;
}

 T3 Farey数列

时间限制：1秒        内存限制：256M

题目描述

对于任何𝑛≥2的整数𝑛的𝐹𝑎𝑟𝑒𝑦数列𝐹𝑛是一组不可约有理数𝑎/𝑏，其中0<𝑎<𝑏≤𝑛以及𝑔𝑐𝑑(𝑎,𝑏)=1，按递增顺序排列。前几个是：

𝐹2={1/2}
𝐹3​​={1/3,1/2,2/3}
𝐹4​​={1/4,1/3,1/2,2/3,3/4}
𝐹5​​={1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5}

你的任务是计算𝐹𝑎𝑟𝑒𝑦数列𝐹𝑛​​中有多少个元素。

输入描述

多组输入。

每组输入一个整数𝑛(2≤𝑛≤106)。输入0时终止。

输出描述

对于每组输入，输出一个整数代表答案。

样例输入

1. 2
2. 3
3. 4
4. 5
5. 0

样例输出

1. 1
2. 3
3. 5
4. 9

其实这个题是在求   

#include<iostream>
#include<cmath>
using namespace std;
const int N = 1e6+10;
int n,t,cnt;
int vis[N],prime[N],/*mu[N],*/phi[N];
long long phi_sum[N];
void sieve(){
    vis[1]=phi[1]=1;
    for(int i=2;i<N;i++){
        if(!vis[i]){
            prime[++cnt]=i;
            // mu[i]=-1;
            phi[i]=i-1;
        }
        for(int j=1;j<=cnt&&1ll*i*prime[j]<N;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                // mu[i*prime[j]]=0;
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            // mu[i*prime[j]]=-mu[i];
            phi[i*prime[j]]=phi[i]*phi[prime[j]];
        }
    }
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    sieve();
    for(int i=2;i<=N;i++){
        phi_sum[i]=phi[i]+phi_sum[i-1];
    }
    while(cin>>n){
        if(!n){
            return 0;
        }
        cout<<phi_sum[n]<<"\n";
    }
    return 0;
}

T4【模板】欧拉降幂 

时间限制：1秒        内存限制：128M

题目描述

求：

𝑎𝑏(𝑚𝑜𝑑 𝑚)

输入描述

三个正整数𝑎,𝑚,𝑏(1≤𝑎≤109,1≤𝑚≤108,1≤𝑏≤1020000000)20000000​​)

输出描述

输出计算结果

样例1输入

1. 2 7 4

样例1输出

1. 2

样例2输入

1. 998244353 12345 98765472103312450233333333333

样例2输出

1. 5333

#include<iostream>
#include<cmath>
using namespace std;
const int N = 1e6+10;
long long a,m;
string b;
long long get_phi(int n){
    int m=int(sqrt(n+0.5));
    int ans = n;
    for(int i=2;i<=m;i++){
        if(n%i==0) {
            ans = ans/i*(i-1);
            while(n%i==0) n/=i;
        }
    }
    if(n>1) ans= ans/n*(n-1);
    return ans;
}
long long depow(string s,long long phi){
    long long b = 0,flag = 0;
    for(int i=0;i<s.size();i++){
        b=b*10+s[i]-'0';
        if(b>=phi){
            flag=1;
            b%=phi;
        }
    }
    if(flag){
        b+=phi;
    }
    return b;
}
long long ksm(long long a,long long b,long long p){
    long long ans = 1;
    while(b){
        if(b&1) ans=(ans*a)%p;
        a=(a*a)%p;
        b>>=1;
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a>>m>>b;
    long long phi=get_phi(m);
    int bb=depow(b,phi);
    cout<<ksm(a,bb,m);
    return 0;
}