快速幂----快速求解底数的n次幂

傷城~ 2024-03-26 18:24 54阅读 0赞

**目录**

一.快速幂

1.问题的引入

2.快速幂的介绍

3.核心思想

4.代码实现

二.Pow(x, n)

1.题目描述

2.问题分析

3.代码实现

三.猴子碰撞的方法数

1.题目描述

2.问题分析

3.代码实现

--------------------

## 一.快速幂 ##

### 1.问题的引入 ###

> 问题:求解num的n次幂,结果需要求余![10^9][10_9]\+7

对于这个问题我们可能就是直接调用函数pow(a,b)来直接求解a的b次幂问题,但是如果求解的结果很大,超过的double的数值范围,我们要求对最终的结果求余![10^9][10_9]\+7,我们如果直接调用pow()函数的话,求解出来的数已经超出了double的最大范围,根本无法求出,这个时候我们是否可以考虑在求解的过程中每一次的结果都求余![10^9][10_9]\+7,而不是只在最终的结果求余![10^9][10_9]\+7这样最终的结果肯定是小于![10^9][10_9]\+7,一定不会超出最大的范围.

### 2.快速幂的介绍 ###

**快速幂:快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N),与朴素的O(N)相比效率有了极大的提高。**

### **3.核心思想** ###

例如计算![3^\{^\{10\}\}][3_10],10的二进制为1010,相当于求解![3^\{1010\}][3_1010]次方

![3^\{^\{10\}\}][3_10]=3\*3\*3\*3\*3\*3\*3\*3\*3\*3

=(3\*3)\*(3\*3\*3\*3\*3\*3\*3\*3)

=![3^\{2\}][3_2]\*![3^\{8\}][3_8]

相当于我们每次对10的二进制的每一个位置求权(如果是二进制这个位是1),则乘以当前的叠加的数,

例如进行求余![3^\{^\{10\}\}][3_10]的步骤 :

**定义变量ans保存![3^\{^\{10\}\}][3_10]的结果 1010位10的二进制表达方式**

**1010的第一位为0,这个时候num=num\*num=![3^\{2\}][3_2]; 二进制形式为:![3^\{0010\}][3_0010]**

**1010的第二位为0,这个时候求权为1,ans=ans\*num=![3^\{2\}][3_2] num=num\*num=![3^\{4\}][3_4];二进制形式为:![3^\{0100\}][3_0100]**

**1010的第三位为0,这个时候num=num\*num=![3^\{8\}][3_8]; 二进制形式为:![3^\{1000\}][3_1000]**

**1010的第四位为1,这个时候求权为1,ans=ans\*num=![3^\{2\}][3_2]\*![3^\{8\}][3_8] num=num\*num=![3^\{16\}][3_16];**

### 4.代码实现 ###

1.求余![10^9][10_9]\+7的版本,返回数据类型为int的结果

public int quickPow(long num,int n){
            long ans=1;
            long mod=1000000007;
            while(n!=0){
                if((n&1)==1)
                    ans=(ans*num)%mod;
                num = num * num % mod;
                n>>=1;
            }
            return (int)(ans%mod);
        }

2.不求余的版本,返回数据类型为long的结果

public long quickPow(long num,int n){
            long ans=1;
            while(n!=0){
                if((n&1)==1)
                    ans=ans*num;
                num = num * num;
                n>>=1;
            }
            return ans;
        }

## 二.Pow(x, n) ##

### 1.题目描述 ###

> 实现 [pow(x, n)][pow_x_ n] ，即计算 `x` 的整数 `n` 次幂函数（即，`xn` ）。

力扣:[力扣][Link 1]

### 2.问题分析 ###

这其实就是一道典型的快速幂的问题,和我们之前不一样的是n可能为负数,负数其实就是![\\frac\{1\}\{x\}^\{-n\}][frac_1_x_-n],可以转化为n为正数的情况,这样就很好求解了

### 3.代码实现 ###

public double myPow(double x, int n) {
            double res = 1;
            if(n<0){
                x=1/x;
                n=-n;
            }
            while (n != 0) {
                if ((n & 1) == 1) {
                    res *= x;
                }
                x *= x;
                n >>>= 1;
            }
            return res;
    
        }

## 三.猴子碰撞的方法数 ##

### 1.题目描述 ###

> 现在有一个正凸多边形，其上共有 `n` 个顶点。顶点按顺时针方向从 `0` 到 `n - 1` 依次编号。每个顶点上 **正好有一只猴子** 。下图中是一个 6 个顶点的凸多边形。
> 
> ![77b3705bad334167b826c55ad7a4b85c.png][]
> 
> 每个猴子同时移动到相邻的顶点。顶点 `i` 的相邻顶点可以是：
> 
>  *  顺时针方向的顶点 `(i + 1) % n` ，或
>  *  逆时针方向的顶点 `(i - 1 + n) % n` 。
> 
> 如果移动后至少有两个猴子位于同一顶点，则会发生 **碰撞** 。
> 
> 返回猴子至少发生 **一次碰撞** 的移动方法数。由于答案可能非常大，请返回对 `109+7` 取余后的结果。
> 
> **注意**，每只猴子只能移动一次。

力扣: [力扣][Link 2]

### 2.问题分析 ###

正难则反,题目问的是至少发生一次碰撞的移动次数,我们不妨把问题转换为求解猴子一次都不碰撞的次数,猴子一共有2的n次幂中跳跃的方式,求中有两种是一次都不碰撞的,一种是猴子全部顺时针进行跳跃,一种是猴子逆时针进行跳跃,所以**猴子至少发生一次碰撞的次数=猴子总共的移动次数-2**

### 3.代码实现 ###

public int monkeyMove(int n) {
            long ans=1,a=2;
            long mod=1000000007;
            while(n!=0){
                if((n&1)==1)
                    ans=(ans*a)%mod;
                a = a * a % mod;
                n>>=1;
            }
            return (int)((ans+mod-2)%mod);
    
        }

## 四.分数求小数 ##

### 1.题目描述 ###

**题目描述**  
小明在尝试把一些分子为1的分数(1/x)转化为小数。使用普通计算器的除法功能可以实  
现，但是保留的小数位数非常有限。而小明希望得到n位小数，而且要从小数点后面第d位  
开始的n位小数。例如，x=13，d=4，n=3时，1/13=0.07692307692....，从小数点后第四  
位开始取三位数，答案是923。现在小明想要计算一些数更大的情况(2<=x<=10000,  
1<=d<=1000000000,1<=n<=10000)，请你写个程序帮帮他。  
**输入描述**  
一行，三个整数x，d，n，用空格隔开，含义如题干。

**输出描述**  
一行，一个字符串，所取的n位数，不需要隔开。  
**样例输入**  
13 4 3  
**样例输出**  
923

### 2.问题分析 ###

### 3.代码实现 ###

public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            long x = sc.nextLong();
            long d = sc.nextLong();
            long n = sc.nextLong();
            long a = 10, b = d - 1;
            long res = 1;
    
            while (b > 0) { // 快速幂
                if ((b & 1) == 1) {
                    res = res * a % x;
                }
                a = a * a % x;
                b >>= 1;
            }
            System.out.println(res);
            for (long i = d; i < n + d; ++i) {
                res *= 10;
                System.out.print(res / x);
                res %= x;
            }
        }

[10_9]: https://latex.csdn.net/eq?10%5E9
[3_10]: https://latex.csdn.net/eq?3%5E%7B%5E%7B10%7D%7D
[3_1010]: https://latex.csdn.net/eq?3%5E%7B1010%7D
[3_2]: https://latex.csdn.net/eq?3%5E%7B2%7D
[3_8]: https://latex.csdn.net/eq?3%5E%7B8%7D
[3_0010]: https://latex.csdn.net/eq?3%5E%7B0010%7D
[3_4]: https://latex.csdn.net/eq?3%5E%7B4%7D
[3_0100]: https://latex.csdn.net/eq?3%5E%7B0100%7D
[3_1000]: https://latex.csdn.net/eq?3%5E%7B1000%7D
[3_16]: https://latex.csdn.net/eq?3%5E%7B16%7D
[pow_x_ n]: https://www.cplusplus.com/reference/valarray/pow/
[Link 1]: https://leetcode.cn/problems/powx-n/description/
[frac_1_x_-n]: https://latex.csdn.net/eq?%5Cfrac%7B1%7D%7Bx%7D%5E%7B-n%7D
[77b3705bad334167b826c55ad7a4b85c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/68225d9a32504ebe81a26f83fcee2157.png
[Link 2]: https://leetcode.cn/problems/count-collisions-of-monkeys-on-a-polygon/description/