2166: 【分治】快速模幂

2166: 【分治】快速模幂

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

题目描述

试求a^b%n的值，其中a、b、n均为整数范围内的数。

输入

三个整数a、b和n

输出

a^b%n的值

样例输入 Copy

1 1 1

样例输出 Copy

0

解析：快速幂模板题

#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;

}