关于欧拉降幂

欧拉降幂

起因是因为牛客多校的一个数论题，需要计算组合数作为次数，即$a^{C_x^t}\mod p$,我在计算C的时候用p作为模数，导致了结果的错误。

洛谷欧拉降幂模板题：

P5091 【模板】扩展欧拉定理 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

欧拉定理：要求a和p互质

证明：欧拉函数 - OI Wiki (oi-wiki.org)

$a^{\phi(p)} \mod p = 1$

则有$a^b \mod p=a^{b\mod\phi(p) }$

扩展欧拉降幂：不要求a和p互质，按照b和$\phi(p)$比较分两类

$a^b \mod p = a^{b}(b<\phi(p))$

$a^b \mod p = a^{(b\mod\phi(p))+\phi(p)}(b<\phi(p))$

故我用一个flag来记录b是否有超过phi(p)的情况，来判断最后是否在次数上加上phi(p)

#include<iostream>
#include<cmath>
using namespace std;
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
ll a,b,med;
#define int ll
ll qpow(ll d,ll c){//快速幂
    ll res = 1;
    while(c){
        if(c&1) res=res*d%med;
        d=d*d%med;c>>=1;
    }return res;
}
int euler_phi(int n){
    int sqr = sqrt(n+0.5);
    int res = n; 
    for(int i=2;i<=sqr;i++){
        if(n%i==0){//找到一个质因子 
            res = res/i*(i-1);//先除后乘，防止越界 
            while(n%i==0) n/=i;//把这个因子从n中消除掉 
        }
    }
    if(n>1) res = res/n*(n-1);//大于sqrt的因子最多只有一个 
    return res; 
}
string s;
signed main(){
    cin>>a>>med;
    ll phi = euler_phi(med);
    cin>>s;
    int siz = s.size();
    b = 0;
    int flag = 0;
    rep(i,0,siz-1){
        b = b*10;
        b = (b+s[i]-'0');
        if(b>=phi) flag = 1;
        b%=phi;
    }
    cout<<qpow(a,b+flag*phi)<<endl;
}
//P5091 【模板】扩展欧拉定理
//https://www.luogu.com.cn/problem/P5091

题解里给的数据加强版，a和m的范围变成了1e12,需要用龟速乘

U55950 【模板】扩展欧拉定理 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

龟速乘

如果x和y直接相乘会爆ll，则可以使用龟速乘。

看代码就很容易理解，即把y按二进制拆分，从低位往高位移动，每次把x乘上2再取模。

ll gui_mul(ll x,ll y){//龟速乘
    ll res = 0;
    while(y!=0){
        if(y&1)res+=x,res%=med;
        x+=x,x%=med;//y的位数每次往上,对应的权值*2
        y>>=1;
    }
    return res;
}

结合龟速乘后的完整代码：

#include<iostream>
#include<cmath>
using namespace std;
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
ll a,b,med;
#define int ll
ll gui_mul(ll x,ll y){//龟速乘
    ll res = 0;
    while(y!=0){
        if(y&1)res+=x,res%=med;
        x+=x,x%=med;
        y>>=1;
    }
    return res;
}
ll qpow(ll d,ll c){//快速幂
    ll res = 1;
    while(c){
        if(c&1) res=gui_mul(res,d);
        d=gui_mul(d,d);c>>=1;
    }return res;
}
int euler_phi(int n){
    int sqr = sqrt(n+0.5);
    int res = n; 
    for(int i=2;i<=sqr;i++){
        if(n%i==0){//找到一个质因子 
            res = res/i*(i-1);//先除后乘，防止越界 
            while(n%i==0) n/=i;//把这个因子从n中消除掉 
        }
    }
    if(n>1) res = res/n*(n-1);//大于sqrt的因子最多只有一个 
    return res; 
}
string s;
signed main(){
    cin>>a>>med;
    ll phi = euler_phi(med);
    cin>>s;
    int siz = s.size();
    b = 0;
    int flag = 0;
    rep(i,0,siz-1){
        b = b*10;
        b = (b+s[i]-'0');
        if(b>=phi) flag = 1;
        b%=phi;
    }
    cout<<qpow(a,b+flag*phi)<<endl;
}
//P5091 【模板】扩展欧拉定理
//https://www.luogu.com.cn/problem/P5091