c++ - 为什么次幂取余可以写成先乘再取余？

浏览：158日期：2023-05-21

问题描述

a的b次方对c取余可以写成下面的形式

int ans = 1;while (b−−){ ans = ( ans∗a)%c ;}

数学不好，求大神解释一下

问题解答

回答1：

因为mod有可乘性

设 a=mq+r, b=nq+s. 则

(a*b) mod q = (mnq^2+msq+nrq+rs) mod q = rs mod q = ((a mod q) * (b mod q)) mod q

手机码字有些混乱

上一条：如何让VS2015 VC++的IntelliSense支持include用.h结尾的文件？下一条：stl - C++ construct源码中 destroy问题

相关文章：
1. javascript - 关于input="file"，重复选择同一文件时不触发change事件的问题2. 为什么矛那里的 <a href=" " 这地方为什么是空的呢？？3. 为什么总是提示我说Template "movieTemplate" not found，我路径都引对了呀4. <tr valign="top"> 看不懂5. mysql - sphinx查询 "中国" 时也能查询到 "中华人民共和国"6. MySQL"="自动 like7. node.js mysql Cannot find module "net" 和 "tls"和"fs" 的问题8. mysql 使用 join 还是 "," 进行多表查询？？？9. mysql - 使用hibernate连接数据库时,数据库版本过高不支持关键字"type" ；10. 发现 <li><a href="/index.php">回到前台</a></li>这样回到首页后，不是登录状态