7-2 快速幂 (10 分)

落日映苍穹つ 2023-10-11 16:24 4阅读 0赞

7-2 快速幂 (10 分)

输入两个整数a、b，求a^b。结果保证在long long int范围内。

#### 输入格式: ####

测试数据有多组，处理到文件尾。每组测试输入两个正整数a，b（1≤a，b≤62）。

#### 输出格式: ####

对于每组测试，输出a^b的结果。

#### 输入样例: ####

2 4

#### 输出样例: ####

**算法分析：**题目的要求结果在长整型范围内，就是在提醒我们要控制运行时间，也暗示着这个题目是要压缩运行时间的， 正常的利用循环也可以求解，但是根据题意嘛，是什么算法，咱就用什么算法，在这里需要用一种快速幂运算的算法，其实也就是分治法的一种应用。

在这里还有一个比较坑的问题，就是他有多组数据，我们是要一直输入的，在C语言中有while（scanf（"%d",&a）!=EOF）,在java中有while（in.hasnext()）来控制输入数据的截止。

**代码实现：**

//C语言实现
    // #include<stdio.h>
    // long quick(long a,long b)
    // {
    //     if(b<=1)return a;
    //     long temp=quick(a,b/2);//这里就是我们分解的步骤。可以结合二分法来看
    //     if(b%2==0)return temp*temp;//偶数计算
    //     else return temp *temp*a;//奇数计算
    // }
    // int main()
    // {
    //     long a,b;
    //     long sum;
    //     while(scanf("%ld %ld",&a,&b)!=EOF)//！！！！！！特别注意
    //     {
    //         printf("%ld\n",quick(a,b));
    //     }
        
    // }
    
    
    //java实现
    import java.util.Scanner;
    public class Main {
        private static long a;
        private static long b;
        public static void main(String [] args)
        {
            Scanner in=new Scanner(System.in);
            while(in.hasNext())
            {
                a=in.nextLong();
                b=in.nextLong();
                System.out.println(quick(b));
            }
            in.close();
        }
    
        public static long quick(long b)
        {
            if(b<=1) return a;
            long temp=quick(b/2);
            if(b%2==0) return temp*temp;
            else return temp*temp*a;
        }
    }