洛谷1226快速幂模板

题目描述

输入b，p，k的值，求b^p mod k的值。其中b，p，k*k为长整型数。

输入输出格式

输入格式：

 

三个整数b,p,k.

 

输出格式：

 

输出“b^p mod k=s”

s为运算结果

 

输入输出样例

输入样例#1： 复制 2 10 9 输出样例#1： 复制 2^10 mod 9=7

*****11的二进制是1011，11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1，因此，我们将a¹¹转化为算 a^(2^0)*a^(2^1)*a^(2^3) 


1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 using namespace std; 6 long long int b,p,k,i,j,ans = 1,ob,op; 7 int main() 8 { 9 scanf("%lld %lld %lld",&b,&p,&k); 10 ob = b; 11 op = p; 12 if(p == 0) 13 { 14 ans = ans % k; 15 } 16 while(p != 0) 17 { 18 if(p & 1 == 1) 19 { 20 ans = ans * b; 21 ans = ans % k; 22 } 23 b = b * b; 24 b = b % k; 25 p >>= 1; 26 } 27 ans = ans % k; 28 printf("%lld^%lld mod %lld=%lld",ob,op,k,ans); 29 return 0; 30 }

 

转载于:https://www.cnblogs.com/rax-/p/9891371.html

总结

以上是生活随笔为你收集整理的洛谷1226快速幂模板的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。