快速幂计算 (简单计算器)

输入

第一行输入n,表示接下来要输入n组;

接下来n行,分别三个,a, b, s, 分别表示要操作的两个数,和操作符号,比如1 2 +,表示1+2,2 1000000000 ^,表示2的1000000000次方;

因为结果可能很大,所以都要与1000000007取模再输出;

输出

输出计算结果,用换行隔开;

C++代码

#include<iostream>
#define ll long long
using namespace std;
ll p = 1000000007;
ll quickpow(ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) ans = ans * a % p;
a = a * a % p, b = b >> 1;
}return ans % p;
}

int main() {
int i;
cin >> i;
while (i) {
ll a, b;
char s;
cin >> a >> b >> s;
if (s == '+') cout << (a % p + b % p) % p << endl;
if (s == '-') cout << (a % p - b % p) % p << endl;
if (s == '*') cout << ((a % p) * (b % p)) % p << endl;
if (s == '^') cout << quickpow(a, b) << endl;
i--;
}return 0;
}


这里重要的是求幂运算,如果是按照常规方法,求幂就是不停的乘自身,复杂度是O(n),通过快速幂,复杂度降为对数级。

在这里关键的是指数b的移位操作,b=b>>1,就是将二进制的b向右边移动一位,举个例子,2的11次方,11的二进制是1011,那2的11次方,就是2的二进制的1011次方,就是2的(8+2+1)次方,其中8,2,1就是二进制的位置的数,根据幂指数运算法则,2^(11)=2^(8+2+1)=2^8*2^2*2^1,相乘的数之间具有规律,都是前一个数位的平方,只要该数在该二进制位是1,这里就要乘以对应的数,每乘一次,二进制b就右移动一位,当b右移到为0,就退出,乘积结束,这就是快速幂的数学原理。

 

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

快速幂计算 (简单计算器)

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 快速幂计算 (简单计算器)
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏