首页 > 代码库 > 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--次方求模(快速求幂取模)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。