欧拉函数和快速幂

欧拉函数：

定义：

互质：互质是公约数只有1的两个整数，叫做互质整数。

欧拉函数：欧拉函数，即 表示的是小于等于n并且和n互质的数的个数。
比如说 φ(1) = 1。当n是质数的时候，显然有 (n)=n-1。

如何求1~n中和n互质的数的个数？

容质原理：

1.从1~n中去掉p1，p2....pk的倍数（此时可能存在多去的情况，例如一个数既是p1的倍数又是p2的倍数）

2.加上所有pi*pj的倍数（此时如果一个数既是p1，p2的倍数又是p3的倍数，此时加三次减三次，没有变化但我们需要去除）

3.减去所有pi*pj*pk

4.加上pi*pj*pk*pd....

依次类推合并得到

，其中p1，p2.....pn是n的质因子

题目：

#include<bits/stdc++.h>
using namespace std;
/*
先试除法分解质因数，在分解过程中如果遇到质因子，那么就用公式计算欧拉函数的结果
*/
int main() {
    int n; cin >> n;
    while(n--){
        int x; cin >> x;
        int res = x;
        for(int i = 2; i < x / i; i++){
            if(x % i == 0){
                // 为了除尽，将res * (1 - 1/i) -> res * (i - 1) / i
                res = res * (i - 1) / i;
                while(x % i == 0) x /= i; 
            }
        }
        if(x > 1) res = res * (x - 1) / x;
        cout << res << '\n';
       
    }
    return 0;
}

 筛法求欧拉函数:

求1~n之间所有数的欧拉函数就可以用筛选法

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6+10;
int cnt,prime[N],phi[N];
bool st[N];
ll get_eulers(int n){
    phi[1] = 1;
    for(int i = 2; i <= n; i++){
        if(!st[i]){
            //质数
            prime[cnt++] = i;
            phi[i] = i - 1;
        }
        // 质数的倍数标记为不是质数
        for(int j = 0; prime[j] <= n / i; j++){
            st[prime[j] * i] = true;
            // Prime[j]是i其中的质因子
            if(i % prime[j] == 0){
                phi[prime[j] * i] = phi[i] * prime[j];
                break;
            }
            phi[prime[j]*i] = phi[i] * (prime[j] - 1);
        }
    }
    ll res = 0;
    for(int i = 1; i <= n; i++) res += phi[i];
    return res;
}
int main() {
    int n; cin >> n;
    cout << get_eulers(n) <<'\n';
    return 0;
}

快速幂：

快速幂：

快速幂算法的目标是计算。传统的做法是通过循环将 a 连续乘 k 次，时间复杂度是 O(k)。但快速幂算法利用了二进制表示的特性，将这个过程优化到了 O(log⁡k)

b个数之间我们不难发现规律：每一个数都是前一个数平方%p。

题目：

#include<bits/stdc++.h>
using namespace std;

int n;
int ksm(int a,int k,int p){
    int res = 1;
    while(k){
        //如果在二进制当中该位是1的话就要累乘到res中
        if(k & 1) res = (ll) res * a % p;
        k >>= 1;// 相当处理下一位
        //每一个数都是前一个数平方%p
        a = (ll)a * a % p;
    }
    return res;
}

int main() {
    scanf("%d",&n);
    while(n--){
        int a,k,p;
        scanf("%d %d %d",&a,&k,&p);
        printf("%d\n",ksm(a,k,p));
    }
    return 0;
}

快速幂求逆元：

对于这类问题，其实就是找到一个数x，能够使得。

根据费马小定理：

我们可以知道对于素数来说，，所以对于a来说。

故对于质数a来说，该逆元就是。

至于无解的情况就是a是p的倍数，此时，不可能为1。

题目：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
int ksm(int a,int k,int p){
    int res = 1;
    while(k){
        //如果在二进制当中该位是1的话就要累乘到res中
        if(k & 1) res = (ll) res * a % p;
        k >>= 1;// 相当处理下一位
        //每一个数都是前一个数平方%p
        a = (ll)a * a % p;
    }
    return res;
}

int main() {
    scanf("%d",&n);
    while(n--){
        int a,p;
        //如果a是p的倍数那么一定无解
        //如果 不是，根据费马定理可以构造出解
        scanf("%d %d",&a,&p);
        int res = ksm(a,p-2,p);
        //p == 2的时候，一定返回的是1
        if(a % p) printf("%d\n",res);
        else puts("impossible");
    }
    return 0;
}