1275: 取余运算

1275: 取余运算

时间限制: 1 Sec   内存限制: 128 MB

题目描述

输入三个正整数a，p，k ，求ap%k 的值。

输入

输入有多组测试例。
对每组测试例，有三个正整数a，p，k （0＜a，p，k2 ＜2^32）

输出

对每组测试例输出1行，是ap%k 的值。

样例输入 Copy

2 10 9

3 18132 17

样例输出 Copy

7

13

解析：

相当于快速幂模板题，具体看博客内快速幂讲解，不多解释。

#include<bits/stdc++.h>

using namespace std;

int main(){

long long a,p,k;

while(scanf("%lld%lld%lld",&a,&p,&k)!=EOF){

long long b=a,ans=1;

while(p){

if(p%2) ans=(ans*b)%k;

b=(b*b)%k;p/=2;

}

printf("%lld\n",ans);

}

return 0;

}