欧拉降幂

说明

在之前的文章中提到过快速幂及其取余的运算

快速幂及其模 - 菜缤的世界 CairBin's Blog

但是有时候对于$ a^{n}\space mod\space m $，n会非常大，这时候我们可能需要用欧拉降幂的方法来处理

正文

原理

欧拉降幂公式如下

$$ a^{n}\space mod \space m = a^{n\space mod \space \varphi (m)+\varphi (m)}\space mod \space m $$

其中 $\varphi (m)$ 为欧拉函数

代码

知道公式后，显然需要抽象几个函数出来

• 快速幂取模

//ll 指 long long int，这里用了个typedef
ll quick_pow_mod(ll a, ll b, ll m)
{
    ll res = 1;
    a %= m;
    while (b) {
        if (b & 1) res = (res * a) % m;
        a = (a * a) % m;
        b >>= 1;
    }
    return res;
}

• 欧拉函数

ll euler_func(ll x) {
    ll e_num = x;
    for (ll i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
        {
            e_num = e_num / i * (i - 1);
            while (x % i == 0)
                x /= i;
        }
    }

    if (x > 1)
        e_num = e_num / x * (x - 1);

    return e_num;
}

利用上面两个函数，可写出欧拉降幂

/*
    欧拉降幂
    a为底数
    n为次幂，这里用字符串存
    m为取模数
*/
ll euler_drop_pow(ll a, string n, ll m)
{
    ll e_num = euler_func(m);
    ll des_power = 0;
    bool flag = false;
    for (ll i = 0; i < n.size(); i++)
    {
        des_power = (des_power * 10 + n[i] - 48) % e_num;
        if (des_power > e_num)
        {
            flag = true;
            des_power %= e_num;
        }
    }

    if(flag)
        des_power += e_num;

    return quick_pow_mod(a, des_power, m);
}

相关习题

• 洛谷P5091