P1226

Aryper · 2021-08-10 12:20:01 · 个人记录

【模板】快速幂||取余运算

快速幂非常的简洁，应用范围也很广，可以做到 O(\log n) 的单次查询。

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<cstring>
using namespace std;

long long ans,b,p,k;

int main()
{

    cin>>b>>p>>k;
    printf("%lld^%lld mod %lld=",b,p,k);
    ans = 1;
    while(p>0) {
        if(p&1)ans=(ans*b)%k;
        b=b*b%k;
        p>>=1;
    }
    printf("%lld",ans%k);
    return 0;
}

然后是光速幂。

相比于快速幂，它的空间复杂度 O(n^{\frac{1}{2}}) ，但可以做到 O(n^{\frac{1}{2}}) 预处理，O(1) 查询，但要求底数与模数不变。

这玩意的原理很简单。

我们知道 a^b=a^{qs+r} ，然后我们可以取 s=\lfloor n^{\frac{1}{2}}\rfloor 。

然后我们只要预处理 a^r(r<s) 以及 a^{qs} ，然后需要的时候相乘即可。

换句话说，a^b=a^{\lfloor \frac{b}{\sqrt{n}}\rfloor\sqrt{n}}\times a^{b\bmod\sqrt{n}} 。

更严谨的做法是：

先运用 a^b\equiv a^{b\bmod \varphi(n)+\varphi(n)} ，即扩展欧拉定理，把指数的范围缩小至 2\varphi(n)<2n 的范围内，然后再使用刚才的光速幂计算。这样可以适应更大的幂运算。

代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=5e4;

ll a,b,p;

ll pow[N+5],powb[N+5];

void init() {
    pow[0]=powb[0]=1;
    for(ll i=1;i<=N;i++) {
        pow[i]=pow[i-1]*a%p;
    }
    for(ll i=1;i<=N;i++) {
        powb[i]=powb[i-1]*pow[N]%p;
    }
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

int main() {

    a=read();b=read();p=read();

    init();

    printf("%lld^%lld mod %lld=%lld",a,b,p,powb[b/N]*pow[b%N]%p);

    return 0;
}