锐客网

  1. 首页 > it技术 > >

算法基础课|AcWing 875 快速幂

数论算法基础课

题目描述：
给定n组ai,bi,pi，对于每组数据，求出ai^bi mod pi的值。
输入格式
第一行包含整数n。接下来n行，每行包含三个整数ai,bi,pi。
【算法基础课|AcWing 875 快速幂】输出格式
对于每组数据，输出一个结果，表示ai^bi mod pi的值。
每个结果占一行。
数据范围
1≤n≤100000,
1≤ai,bi,pi≤2?10^9
输入样例：

2 3 2 5 4 3 9

输出样例：
4 1

分析：
首先，为了后面的推理方便，引入下同余的概念。给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系。有如下性质：
模p加法：(a + b) % p = (a%p + b%p) % p
模p减法：(a- b) % p = (a%p- b%p) % p
模p乘法：(a* b) % p = ((a % p)*(b % p)) % p
幂模p： (a^b) % p = ((a % p)^b) % p
要求a^n，如果暴力求解就是将a乘上n-1个a，表面上时间复杂度是O（n），但是乘法运算的代价是十分高昂的，复杂度与其说是O（n），不如说是O(2^k)，其中k = logn，也就是n的字宽度。而快速幂求解乘方运算的时间复杂度为O（k）。
要求a^b，对于b，可以进行二进制展开，比如b = 11时，即(1011)2，b = 1 * 2^0 + 1 * 2^1 + 0 * 2^2 + 1 * 2^3 = 11.如果用十进制来看，就是11 = 8 + 2 + 1，a^11 = a^(8+2+1) = a^8 * a^2 * a^1.所以求快速幂的过程就是对b的二进制表示自右向左逐个计算的过程。只要b对应位为1，此刻，ans就应该乘以此时的权重，b每次右移取末尾，对应a^b也就是a不断平方的过程。
从复杂度层面分析，之前暴力的做法需要计算a，a^2,a^3,...；而快速幂只需要计算a的2^i幂，因此复杂度是对数级别的。
#include using namespace std; typedef long long ll; ll binaryPow(ll a,ll b,ll p){ ll ans = 1 % p; while(b){ if(b & 1)ans = ans * a % p; a = a * a % p; b >>= 1; } return ans; } int main(){ int n; cin>>n; while(n--){ int a,b,p; cin>>a>>b>>p; cout<


    推荐阅读


    上一篇：市场调研|中国数字文化产业前景规划及未来重点发展方向报告2022～2028年

    下一篇：算法提高课|AcWing 1086 恨7不成妻