快速幂&快速乘法
2024-09-30 03:05:56
尽管快速幂与快速乘法好像扯不上什么关系,但是东西不是很多,就一起整理到这里吧
快速幂思想就是将ax看作x个a相乘,用now记录当前答案,然后将指数每次除以2,然后将当前答案平方,如果x的2进制最后一位为1的话,就将答案乘以现在的数。快速乘法类似,只是将a*x看作x个a相加。
代码
#include<cstdio>
#include<iostream>
using namespace std;
int mi(int a,int x)
{
int ans=;
for(int now=a;x>=;x>>=,now=now*now)//a表示底数,x表示次数
{
if(x&) ans=ans*now;
}
return ans;
}
int cheng(int a,int x)//表示a*x
{ int ans=;
for(int now=a;x>=;now=now*,x>>=)
{
if(x&) ans=ans+now;
}
return ans;
}
int main()
{
int a,x;
scanf("%d%d",&a,&x);
printf("快速幂 %d\n",mi(a,x));
printf("快速乘法 %d\n",cheng(a,x));
return ;
}
最新文章
- SpringMVC和MyBatis整合
- linux启动流程及自定义gurb
- 服务器上index.jsp变空
- 初步理解JNDI
- 动画库Animate.css
- 在C++工程中设置全局函数
- POJ 2063 Investment 完全背包
- Period(KMP,循环节问题)
- OpenCV之邻域运算之最值滤波
- 【BZOJ】1001: [BeiJing2006]狼抓兔子 Dinic算法求解平面图对偶图-最小割
- STM32库函数实现方法
- UFLDL教程(六)之栈式自编码器
- jQuery也能舞出绚丽的界面(完结篇)
- 超出区域文字显示为省略号或者剪切效果——CSS的生僻操作
- Android sdk配置 常见问题及处理方法
- Dapper数据库相关操作
- Sphinx学习笔记(一)
- BZOJ 2957: 楼房重建 [线段树 信息合并]
- 【gedit】 显示行号
- JaveWeb 公司项目(5)----- Java获取当前时间的年月日以及同Thrift格式的转化