跳到主要内容

剩余系-欧拉定理-扩展欧拉定理

剩余类​

给定一个正整数n,把所有整数根据模n的余数r∈[0,n-1]分为n类，每一类表示为C=nx+r的形式，这类数所构成的一个集合称为模n的剩余类例n=5,r=3,则C3=5x+3为模5的一个剩余类。

完全剩余系​

给定一个正整数n,有n个不同的模n的剩余类，从这n个不同的剩余类中各取出一个元素，总共n个数，将这些数构成一个新的集合，则称这个集合为模n的完全剩余系 例n=5,则1234是一个模5的完全剩余系，{5,1,-3,8,9}也是一个模5的完全剩余系。

简化剩余系​

给定一个正整数n,有p(n)个不同的模n的余数r与n互质的剩余类，从这p(n)个剩余类中各取出1个元素，总共p(n)个数，将这些数构成一个新的集合，则称这个集合为模n的简化剩余系 例n=5,则4是一个模5的简化剩余系， n=10,则9是一个模10的简化剩余系 显然模n的简化剩余系中所有的数都与n互质

欧拉函数​

1-n中与n互质的数的个数称为欧拉函数，记为ψ(n)\psi(n),ψ(n)=n(1−1p1)(1−1p2)⋅⋅⋅(1−1pk)\psi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})···(1-\frac{1}{p_k})

欧拉定理​

若gcd(a,m)=1gcd(a,m)=1,即a和m互质，则aψ(m)≡1( mod m)a^{\psi(m)} \equiv 1(\bmod m) 例如a=3,m=4,则3ψ(4)≡32≡1( mod 4)3^{\psi(4)} \equiv 3^2 \equiv 1(\bmod 4) 当m为质数是，ψ(m)=m−1\psi(m)=m-1,即1-（m-1）每个数都和m互质，带入可得am−1≡1( mod m)a^{m-1} \equiv 1(\bmod m),即为费马小定理

扩展欧拉定理​

ab≡{ab,b<φ(m),( mod m)ab mod φ(m)+φ(m),b≥φ(m),( mod m)a^{b} \equiv\left\{\begin{array}{lll} a^{b}, & b<\varphi(m), & (\bmod m) \\ a^{b \bmod \varphi(m)+\varphi(m)}, & b \geq \varphi(m), & (\bmod m) \end{array}\right.

题目​

https://www.luogu.com.cn/problem/P5091 求ab mod ma^b \bmod m b非常大 【样例 11 解释】 24 mod 7=22^4 \bmod 7 = 2 【数据范围】 对于 100%100\% 的数据，1≤a≤1091\le a \le 10^9，1≤b≤1020000000，1≤m≤1081\le b \le 10^{20000000}，1\le m \le 10^8。

代码​

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define debug(x) cout<<"a["<<x<<"]="<<a[x]<<endl;
#define pr(x) cout<<x<<endl;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 2e8 + 10;

char s[N];

//快速幂算法
LL qmi(LL a,LL k,LL p){
    LL res=1;
    while (k){
        if (k&1) res=res*a%p;
        a=a*a%p;
        k>>=1;
    }
    return res;
}

//试除法求欧拉函数
// phi(n)=n*i/(i-1)...
int phi(int n){
    int res=n;
    for(int i=2; i<=n/i; i++){
        if(n%i == 0){
            res = res/i*(i-1);
            while(n%i == 0) n /= i;
        }
    }
    if (n>1) res=res/n*(n-1);
    return res;
}

//扩展欧拉函数降幂
int downpow(int phi){
    int b=0;
    bool flag=false;
    for(int i=0;s[i];i++){
        //将b算出来，不会算很大
        b=b*10+(s[i]-'0');
        if (b>=phi) {
            flag=true;
            b%=phi;
        }
    }
    if (flag) b+=phi;
    return b;
}


int main() {
    IOS;
#ifndef ONLINE_JUDGE
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.in", "r", stdin);
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.out", "w", stdout);
#endif
    int a,m;
    cin>>a>>m>>s;
    int t= phi(m);
    int b= downpow(t);
    pr(qmi(a,b,m))

    return 0;
}
0%