SDNU 1056.A ^ B Problem【高速幂取余】【8月12】
SDNU 1056.A ^ B Problem【快速幂取余】【8月12】
赤裸裸的快速幂。之前不知道该怎么做快速幂。
A ^ B Problem
Description
给定三个数A, B, K, 求 A的B次方除以K的余数 。
Input
输入只有一行，为三个正整数A(1 <= A <= 2000000000), B(1 <= B <= 2000000000), K(1 <= K <= 10000)。
Output
一个整数，(A ^ B) % K 的值。
Sample Input
11 100 7
Sample Output
4
利用公式a*a%c=((a%c)*a)%c,这样每一步都进行这种处理，这就解决了a^b可能太大存不下的问题。
#include<cstdio>
int main(){
long long A,B,K;
scanf("%lld%lld%lld",&A,&B,&K);
long long ans=A;
for(int i=1;i<B;i++)
ans=(ans%K)*A%K;
printf("%lld\n",ans);
return 0;
}
但是时间复杂度并没有优化，所以肯定会超时。
快速幂算法依赖于以下明显的公式：
#include<cstdio>
int mod(int a,int b,int k){
int ans=1;
a=a%k;
while(b>0){
if(b%2==1) ans=(ans*a)%k;
b/=2;
a=(a*a)%k;
}
return ans;
}
int main(){
int A,B,K;
scanf("%d%d%d",&A,&B,&K);
printf("%d\n",mod(A,B,K));
return 0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。