(1)当我们求一个数的n次方的的结果时,若直接选择for循环,来累乘的话,效率很低,时间复杂度位O(n),而当我们选择快速幂来计 算时,时间复杂度能达到O(logn),快了很多。快速幂的基本方法基于二进制,将n次方分解,每次计算平方。如下:
假设我们要求5^23(5的23次方),因为23换为二进制为:10111。即2^4*1+2^3*0+2^2*1+2^1*1+2^0*1,那么5^23次方就可以转换,为:5^(2^4*1)*5^(2^3*0)*5^(2^2*1)*5^(2^1*1)*5^(2^0*1)。基于这个公式,我们计算5^23次方就只需要5步就算出来了,原来则需要计算23次。效率提高不少，特别是当n为很大的时候,效率更高。那么,现在有个问题,怎么算这五步呢?思路如下:
1.观察这五个等式,从高到低依次为5^16,5^8(虽然没有,但规律是这样),5^4,5^2,5^1[前一项是后一项的平方]
2.我们可以通过&1来得到一个数的最后一位,可以通过>>符号将二进制往右边移一位。
有了上面两点,我们来实现快速幂的算法:
结论:算法不复杂,主要是&和>>符号的应用，然后就是每次移动一位,就应该平方一次,因为前面的数是后面的数的平方，即使二进制最后一位为0,也应平方一次,因为它前一个的前面一个是它的平方的平方，也就是4次方。
**2.大整数的大整数幂对一个大整数求幂的结果**1.这个问题也是基于上面的部分算法,不过要复杂一点。首先我们需要知道的是对一个数求模有以下的公式:
(a + b) % p = (a % p + b % p) % p （1）
(a - b) % p = (a % p - b % p) % p （2）
(a * b) % p = (a % p * b % p) % p （3）
(a ^ b) % p = ((a % p)^b) % p （4）
上面的公式就是说，一个数求模,可以分别对构成这个数的各个数求模,然后将模进行相应的加减乘除来计算结果。
例如:(5^131287)%4，我们不可能把5^131287次方算出来,就算用计算机，这个数也是超越了计算范围了,特别大。根据以上公式,我们知道5%4=1,(1^131287）%4=1。所以结果为1。
再比如:(16^23234)%7,因为16%7=2,所以可以转换为求(2^23234)%7，然后我们知道(2^3)%7=1,而23234=3*7744+2。所以(2^23234)%7=( (2^3)^7744 * (2^2) )%7=1*4=4。所以结果为4
有了以上的基础,我们可以得到以下的算法:
public class Main{ public static void main(String [] args){ long n,k,m; Scanner sc=new Scanner(System.in); n=sc.nextLong(); k=sc.nextLong(); m=sc.nextLong(); Main main=new Main(); long res=main.mod(n, k,m); System.out.println(res); } long mod(long n,long k,long m){ long mod=1; long base=n; long res=1; if(n>m){//先减小以下n的值,不然容易超long的范围 n=n%m; base=n; }else if(n==m) { return 1; } while(k!=0){ if((k&1)==1){ //取k的二进制最后一位,若为1,则表示存在该项 mod*=(base%m); if(mod==0){ return 0; //只要有一个数模为0,直接返回0 }else if(mod>m){ mod%=m; //若模大于除数,则可以进行一次求模 } base=base%m; //base求余,根据余数来算模,以免超出long的范围 } base*=base; //将余数进行平方来算模,能减小数的大小 base=base%m; k>>=1; //将k的二进制往右移动一位 } return mod; }}546471837123713的6464713次方对764求模的结果:
结论:感觉这个可能理解有点困难,不过有数论基础的话理解应该不难的。没接触过数论的话，要好好理解下