俄罗斯乘法
【摘要】 俄罗斯乘法：
俄罗斯乘法是用于计算两个数相乘，一般多用于取模的情况，可以将其转化为快速幂的形式。
公式：
举个例子：计算 35*72
过程
35 72
17 144
8 288
4 576
2 1152
1 230...
俄罗斯乘法：
俄罗斯乘法是用于计算两个数相乘，一般多用于取模的情况，可以将其转化为快速幂的形式。
公式：
举个例子：计算 35*72
过程
35 72
17 144
8 288
4 576
2 1152
1 2304
从上到下，对每一行，若左边的数字若为奇数，则将右边的数字取出，累加。
72+144+2304=2520
累加的结果2520即为乘积。
这样可以结合快速幂来求（取模的情况）：
-
int Pow(int n1 ,int n2 ,int p){
-
int ans = 0 ;
-
while(n1){
-
if(n1&1)
-
ans = (ans + n2%p)%p ;
-
n1 = n1>>1 ;
-
n2 = (n2<<1)%p ;
-
}
-
return ans ;
-
}
文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nyist_zxp/article/details/51173807
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）