问题描述 有一天，JOE终于不能忍受计算ab%c这种平凡的运算了。所以他决定要求你写一个程序，计算ab%c。
提示：若b为奇数,，ab=(a(b/2))2*a，否则ab=(a(b/2))2。 输入格式 三个非负整数a,b,c； 输出格式 一个整数ans，表示a^b%c； 样例输入 7 2 5 样例输出 4 数据规模和约定 30% a <= 100, b <= 10^4, 1 <= c <= 100 60% a <=10^4, b <= 10^5, 1 <= c <= 10^4 100% a <=10^6, b <= 10^9, 1 <= c <= 10^6
思想：快速幂
#include<stdio.h> #include<iostream> using namespace std; typedef long long ll; int main() { ll a,b,c; ll sum=1; scanf("%I64d%I64d%I64d",&a,&b,&c); while(b) { if(b%2==1) sum=sum*a%c; a=a*a%c; b/=2; } printf("%I64d",sum); return 0; }