首页 > 代码库 > NYOJ--102--次方求模(快速求幂取模)

NYOJ--102--次方求模(快速求幂取模)

次方求模

时间限制:1000 ms  |  内存限制:65535 KB
难度:3
 
描述

求a的b次方对c取余的值

 

 
输入
第一行输入一个整数n表示测试数据的组数(n<100)
每组测试只有一行,其中有三个正整数a,b,c(1=<a,b,c<=1000000000)
输出
输出a的b次方对c取余之后的结果
样例输入
3
2 3 5
3 100 10
11 12345 12345
样例输出
3
1
10481
 1 /*
 2     Name: NYOJ--102--次方求模
 3     Copyright: ?2017 日天大帝
 4     Author: 日天大帝 
 5     Date: 28/04/17 20:31
 6     Description: 快速求幂取模
 7 */
 8 #include<iostream>
 9 using namespace std;
10 const int MAX = 1e8;
11 int pow(long long int n,long long int p,long long int c) {
12     int m = 1;
13     while(p > 0){
14         if(p & 1)
15             m = ((m%c) * (n%c)) %c;
16         n = ((n%c)*(n%c)) %c;
17         p = p>>1;
18     }
19     return m;
20 }
21 int main(){
22     ios::sync_with_stdio(false);
23     int n;cin>>n;
24     while(n--)    {
25         int a,b,c;
26         cin>>a>>b>>c;
27         cout<<pow(a,b,c)<<endl;
28     }
29     return 0;
30 }

 

公式求幂→二分求幂→快速求幂→快速求幂取模 

直接用C语言的库函数pow()(别忘了它的头文件#include<math.h>),似乎很简单,但是它的时间复杂度高达O(n)。 
显然,这很容易超时。 
于是有了下面的二分求幂(时间复杂度O(lgn))

二分求幂的原理可以用下面这张图表示 
技术分享

用递归来实现,虽然代码有点长,但是很好理解

 1 int pow(int a,int n)//返回值是a的n次方
 2 {
 3     if(n==0)//递归终止条件
 4         return 1;
 5     if(n==1)
 6         return a;
 7     int result=pow(a,n/2);//二分递归
 8     result=result*result;//这部分奇数偶数都一样
 9     if(n%2==1)//如果n是奇数,就要多乘一次
10         result=result*a;
11     return result;
12 }

 

用非递归,更加简洁

 1 int pow(int a,int n)//返回值是a的n次方
 2 {
 3     int result=1;
 4     while(n!=0)
 5     {
 6         if(n%2==1)//如果n是奇数
 7             result=result*a;//就要多乘一次
 8         a=a*a;
 9         n=n/2;//二分
10     }
11     return result;
12 }

快速幂顾名思义比二分幂又快一些, 
快速幂借助了强大的位运算,时间复杂度达到O(log?N)。 
用非递归的代码实现

 1 int pow(int a,int n)//返回值是a的n次方
 2 {
 3     int result=1,flag=a;
 4     while(n!=0)
 5     {
 6         if(n&1)//如果n是奇数,即n的二进制最末位为1时
 7             result=result*flag;
 8         flag=flag*flag;
 9         n=n>>1;//n的二进制右移一位,即n/2
10     }
11     return result;
12 }

当然还能用递归来实现,但是太复杂,我没学会…

刷题中让直接求幂的不多,求幂后取模的却不少,毕竟求幂结果太大了。 
水平所限,只会用二分幂取模,时间复杂度与二分幂一样O(lgn)。 
基本可以在各种比赛中顺利通过,也是目前比较常用的方法

原理同样很简单,都是小学学过的:积的取余等于取余的积取余 
接下来用代码实现

 1 int pow(int a,int n,int b)//返回值是a的n次方对b取余后的值
 2 {
 3     int result=1;
 4     a=a%b;//积的取余等于取余的积取余
 5     while(n>0)
 6     {
 7         if(n%2==1)
 8             result=result*a%b;//n是奇数的话就要多乘一次,原理和前面的二分求幂一样
 9         n=n/2;//二分
10         a=a*a%b;//积的取余等于取余的积取余
11     }
12     return result;
13 }

影响计算机效率的是运算次数,而不是运算结果。 
所以前面几个算法都是通过增大运算结果,减少运算次数,提高计算机效率。

NYOJ--102--次方求模(快速求幂取模)