整数的快速幂
//递归写法
int fastpow(int a,int p)
{
if(p==0)
return 1;
if(p%2==1)
{
int temp=fastpow(a,(p-1)/2);
return temp*temp*a;
}else{
int temp=fastpow(a,p/2);
return temp*temp;
}
}
//非递归写法
int fastpow(int a,int p)
{
int ret=1;
while(p>0)
{
if(p%2==1)
ret=ret*a;
a=a*a;
p>>=1;
}
return ret;
}
能在
O(log n)的时间内通过,当数很大时,必要的时候要进行取模运算,因为某个因子取余之后相乘再取余保持余数不变,那么新算得的数也可以进行取余,所以得到比较良好的改进版本,例,
int ans = 1;
a = a % c; //加上这一句
for(int i = 1;i<=b;i++)
{
ans = ans * a;
}
ans = ans % c;
简单的整数快速幂的题
http://poj.org/problem?id=1995
http://acm.hdu.edu.cn/showproblem.php?pid=2035
HDU2035代码
import java.util.Scanner;
public class Main
{
Scanner scan=new Scanner(System.in);
int m=1000;
public static void main(String[] args)
{
new Main().run();
}
void run(){
while(true)
{
int a=scan.nextInt();
int b=scan.nextInt();
if(a==0&&b==0)
break;
else{
fastpow(a,b);
}
}
}
void fastpow(int a,int b){
long c=1;
while(b>0)
{
if(b%2==1)
c=(c*a)%m;
a=(a%m)*(a%m);
b>>=1;
}
System.out.println(c);
}
}
分享到:
相关推荐
利用vjudge源码改造爬虫抓取vjudge全局共享答案资源。 ACMer,请用于参考思路,对拍代码,不要直接提交。
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个...
很多经典的杭电oj与poj习题的ac代码与详解!全部ac,决对没有错误的代码!
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
自动探测POJ、HDU、SOJ、ZOJ水题,对于有志于刷遍各种水题的ACMer来说非常有用
2遍dp poj_3613解题报告 poj_3613解题报告
有题,有解题思路,有解题代码 hdu2516、poj1067和hdu1527、hdu2177、hdu2176等等
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
判断某整数是否为2的整数次幂 问题转化为:判断整数是否为正整数且二进制中仅存在一位1 (n > 0 && (n & (n - 1)) == 0) 链表节点交换 修改next指针的值进行节点的交换 修改val字段的值 等价节点交换 练习: leetcode...
poj分类poj分类poj分类poj分类
自己写得大数浮点数幂运算(c++实现),系poj acm 的problem:1001的实现
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
杭州电子科技大学OJ分类,很适合刚入门的新手哦,分类很详细,是不可多得的资料