POJ1995&& HDU2035 整数快速幂

整数的快速幂

	//递归写法
		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);
    }
}