5208 求乘方取模

时间限制: 1 s

空间限制: 1000 KB

题目等级 : 未定级

题目描述 Description

给定非负整数A、B、M，求(A ^ B) mod M。

输入描述 Input Description

包含多组输入，输入处理到EOF。

每组输入仅一行，三个用空格隔开的非负整数A、B、M。

输出描述 Output Description

对于每组输入，输出一行，一个非负整数，即(A ^ B) mod M。

样例输入 Sample Input

2 3 100006

32 71 83

900 800 777

样例输出 Sample Output

8

5

219

数据范围及提示 Data Size & Hint

0 <= A, B < 8 * 10^18。

0 < M < 8 * 10^18。

保证A和B不同时为0。

/*

快速幂.

快速乘法防爆.

*/

#include<iostream>

#include<cstdio>

#define LL unsigned long long

using namespace std;

LL a,b,k;

LL Mul(LL a,LL b,LL c)

{

    LL ans=0;

    while(b)

      {

        if(b&1)

          {

            b--;ans+=a;ans%=c;

          }

        b>>=1;a<<=1;a%=c;

      }

    return ans;

}

LL fast_mi(LL a,LL b,LL k){

    LL tot=1;

    while(b){

        if(b&1) tot=Mul(tot,a,k);

        a=Mul(a,a,k);

        b>>=1;

    }

    return tot;

}

int main()

{

    while(cin>>a>>b>>k){

        if(!a)printf("0\n");

        else if(!b) {

            cout<<1%k;printf("\n");

        }

        else {

            cout<<fast_mi(a,b,k);

            printf("\n");

        }

    }

    return 0;

}