题解 【P5091】 【模板】扩展欧拉定理

题面

https://www.luogu.com.cn/problem/P5091

基本思路

(根据题解可知)这题用欧拉降幂+快速幂解决.

下面开始介绍 温馨提示: 为了您的阅读体验, 请坐和放宽, 等待图片加载完成

扩展欧拉定理

公式如下, 证明请自行查阅资料:

公式在膜m意义下成立(才不会说是我打LaTeX的时候忘记加了 已经加上了)

套用上面的公式, 我们现在只需要求出欧拉函数的值即可

欧拉函数

定义见各大百科, 下面推导一个式子用于编程:

首先是欧拉函数的两个性质(下面的p是一个质数):

我们很容易推导出下面的式子:

代码正确性

首先我们根据数论知识可以知道, 判断质数时只要试到 √n 即可. 当试出一个因子时, 我们用一个循环尝试继续提取这个因子, 因此, 每试出一个因子, n的唯一分解式就减少了一项(也就是减少了一个 p_m^k_m ). 因为我们是从小到大尝试的, 所以必然不会试出合数因子(拆分成更小的质数在之前的循环中被剥离了). 这里有个问题, 如果 n 是质数, 不会引起ans的变化, 因此, 循环结束后需要特判.

点我查看完整代码

inline int phi(int n){
    int ans = 1, num = 1;
    for(int i = 2; i * i <= n; i++){
        if (!(n % i)){
            num = i - 1;
            n /= i;
            while(!(n % i)){
                num *= i;
                n /= i;
            }
            ans *= num;
        }
    }
    if (n != 1){
        ans *= n - 1;
    }
    return ans;
}

快速幂

详见传送门: P1226 【模板】快速幂||取余运算

完整AC代码

点我查看完整代码

#include<cstdio>
using namespace std;
typedef long long ll;

inline int qpow(int b, int p, int mod){
    ll pow = b, temp = p, ans = 1;
    for ( ; temp; temp >>= 1){
        if (temp & 1){
            ans *= pow;
            if (ans > mod)	ans %= mod;
        }
        pow *= pow;
        if (pow > mod)	pow %= mod;
    }
    return ans % mod;
}

inline int read(int mod){
    int x = 0, flag = 0;
    char c = getchar();
    while(c < '0' || c > '9')	continue;
    while(c >= '0' && c <= '9'){
        x = (x << 3) + (x << 1) + (c ^ 48);
        if (x >= mod){
            x %= mod;
            flag = 1;
        }
        c = getchar();
    }
    return x + (flag ? mod : 0);
}

inline int phi(int n){
    int ans = 1, num = 1;
    for(int i = 2; i * i <= n; i++){
        if (!(n % i)){
            num = i - 1;
            n /= i;
            while(!(n % i)){
                num *= i;
                n /= i;
            }
            ans *= num;
        }
    }
    if (n != 1){
        ans *= n - 1;
    }
    return ans;
}

int main(){
    int a, b, mod, cs;
    scanf("%d%d ", &a, &b);
    mod = phi(b);
    cs = read(mod);
    printf("%d", qpow(a, cs, b));
    return 0;
}