欧拉函数

欧拉函数表示为 从1 ~ n 内所有互质的数 的个数

公式法法求欧拉函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int phi(int x)
{
    int res = x;
  	// 我们只取较小质因子
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
  
  	// 检查是否包含大于根号x的质因子并带入公式
    if (x > 1) res = res / x * (x - 1);

    return res;
}

筛法求欧拉函数

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
32
33
const int N = 1e6 + 10;

int prime[N];
int st[N];
int eul[N];
int cnt;

void  get_eul(int n)
{
    eul[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        if(!st[i])
        {
            prime[cnt++] = i;
            eul[i] = i - 1;
        }
        
        for(int j = 0; prime[j] <= n / i; j++)
        {
            st[prime[j] * i] = 1;
            
            if(i % prime[j] == 0)
            {
              	// 通过欧拉函数公式变形可得
                eul[prime[j] * i] = prime[j] * eul[i];
                break;
            }
          	// 同理公式变形
            eul[prime[j] * i] = (prime[j] - 1) * eul[i];
        }
    }
}

推导过程

快速幂

二进制优化指数

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
32
33
34
35
#include<iostream>

using namespace std;

// a ^ k % p
long long qmi(int a, int k, int p)
{
    long long ret = 1;
  
  	// 二进制优化k, 判断最后一位是否是1;
    while(k)
    {
      	// 判断最后一位是否是1
        if(k & 1) ret = (long long)ret * a % p;
        k >>= 1;
      
      	// 指数乘以2
        a = (long long)a * a % p;;
    }
    
    return ret;
}

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int a, k, p;
        cin >> a >> k >> p;
        cout << qmi(a,k,p) << endl;
    }
    return 0;
}

快速幂求逆元

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
32
#include<iostream>
#include<algorithm>

using namespace std;

int qmi(int a, int k, int p)
{
    int ret = 1;
    while(k)
    {
        if(k & 1) ret = (long long)ret * a % p;
        k >>= 1;
        a = (long long) a * a % p;
    }
    return ret;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int a, p;
        cin >> a >> p;
        int t = qmi(a, p - 2, p);
        if(a % p != 0) cout << t << endl;
        else cout << "impossible" << endl;
    }
    
    return 0;
}

531676889568_.pic

扩展欧几里得算法