题解 P1226 【取余运算||快速幂】

荣一鸣 · 2018-07-09 14:29:09 · 题解

快速幂模板题（只是单纯的求快速幂）

快速幂原理：

对于a^b来说，

如果b%2==1，那么b=2 * n+1(n是非负整数)，

则a^b=(a^n)^2*a.

如果b%2==0，那么b=2 * n

则a^b=(a^n)^2;

快速幂取模：

对于c=a*b来说，c%k = (a*b)%k = (a%k) * (b%k) % k

所以在运算快速幂取模时，可以用递归或递推，用log2n的时间算出 a^b%k

#include<bits/stdc++.h>
using namespace std;
long long b,a,p,k,ans=1,c;
int main()
{
    scanf("%d%d%d",&b,&p,&k);
    a=b;c=p;
    while(p>0)
    {
        if(p%2!=0)
            ans=ans*b%k;
        b=b*b%k;
        p=p/2;
    }
    ans%=k;
    printf("%d^%d mod %d=%d",a,c,k,ans);
    return 0;
}