求乘方取模（快速幂+慢速乘法模板）

2019-04-14 18:50发布

站内文章 / 模拟电子
16385 0 948

求乘方取模

题目描述：
给定非负整数A、B、M，求(A ^ B) mod M。
输入描述 Input Description
包含多组输入，输入处理到EOF。
每组输入仅一行，三个用空格隔开的非负整数A、B、M。
输出描述：
对于每组输入，输出一行，一个非负整数，即(A ^ B) mod M。
样例输入：
2 3 100006
32 71 83
900 800 777
样例输出：
8
5
219
数据范围及提示：
0 <= A, B < 8 * 10^18。
0 < M < 8 * 10^18。
保证A和B不同时为0。 #include #include using namespace std; unsigned long long a,b,m; unsigned long long quick_mul(unsigned long long a,unsigned long long b,unsigned long long mod)//慢速乘法模板 { unsigned long long ans=0; while(b) { if(b&1) { b--; ans=(ans+a)%mod; } b>>=1; a=(a+a)%mod; } return ans; } unsigned long long quick_mi(unsigned long long a,unsigned long long b,unsigned long long mod)//快速幂模板 { unsigned long long ans=1; while(b) { if(b&1) ans=quick_mul(ans,a,mod); b>>=1; a=quick_mul(a,a,mod); } return ans; } int main() { while(cin>>a>>b>>m)//a^b%m cout<return 0; }

热门文章