那个网站做稻草交易网站域名查询网

快速幂求解a^b%p

(1)题目内容

求a的b次方对p取模的值

(2)输入格式

三个整数a,b,p，在同一行用空格隔开。

(3)输出格式

输出一个整数，表示a^b mod p的值。

(4)数据范围

1≤a,b,p≤10ⁿ(n=9)

(5)输入样例

3 2 7

(6)输出样例

2

(7)分析

直接循环容易程序运行超时

快速幂基本思想

//分析
①3^7=？7 = 111
3^1 = 3
3^2 = 9
3^4 = 81（凑次方）
3^7 = (3^1)*(3^2)*(3^4)② 3^9 = ?
9 = 1001
3^1 = 3
3^2 = 9
3^4 = 81
3^8 = 6561
3^9 = (3^1)*(3^8)//1001所以 3^1000000 = 
1000000 = (写出其二进制)
3^1 = 3
3^2 = 9
3^4 = 81
3^8 = 6561
3^16 
...
3^(2^19) = 

(8)代码实现

#include<iostream>
//#include<bits/stdc++>//万能头文件，但编译时间会变慢,所以简单程序就能不写就不写
using namespace std;int main(){int a,b,p;cin>>a>>b>>p;int res = 1%p;//为什么要%p? 因为若b=0，则直接不进入下面的循环while(b){if(b&1) //b&1  即取b的个位数res = res * 1ll * a % p;  //1ll 强制类型转换 因为res*a可能会发生溢出，所以强制类型转换为long long 类型a = a * 1ll * a % p;  //b的十位是每次循环进行平方 b>>=1;  //去掉个位}cout<<res<<endl;return 0;}

(9)快速幂解题模板

//求 m^k mod p，时间复杂度 O(logk)。int qmi(int m, int k, int p)
{int res = 1 % p, t = m;while (k){if (k&1) res = res * t % p;t = t * t % p;k >>= 1;}return res;
}