快速幂的秘密

编程入门行业动态更新时间:2024-10-10 05:23:03

快速幂的<a href=https://www.elefans.com/category/jswz/34/1770835.html style= 秘密"/>

快速幂的秘密

原文链接：/

原理

先举个例子，比如说算3^{6,你要怎么算，用6个6相乘对不对，那要是3}1000呢？1000个3相乘，复杂度为O(N)，现在我们这样算，6的二进制是110，所以6=1*(2^2)+1*(21)+0*(2^0)，那么36就变成了3^( 1*(2^2)+1*(21)+0*(2^0) )=3^(1*(22)) * 3^(1*(21)) * 3^(0*(20))，这其实就是快速幂的原理，看起来麻烦了对吗？OK，先不看复杂度，先看用代码如何实现，我们可以用一个数来充当3^(1*(22))、3^(1*(21))、3^(0*(20))，在下面的代码中y就是这个变量，不是每一次都要算的，比如3^(0*(20))=1，乘不乘都一样，那怎么判断呢？我们每次取二进制数的最后一位，要么是0要么是1，如果是0，就不用不用乘，否则就乘，先看代码：

int p(int a,int b){int t,y;  //定义两个变量，t起到类乘的作用，而y则就是每一次要乘的数t=1; y=a;  //注意一定要初始化while (b!=0){  //只要二进制位数还没有遍历完就还要循环if (b&1==1) t=t*y; //y就是幂的形式a^(2^0),a^(2^1),a^(2^2),a^(2^3)y=y*y;  //b=b>>1;  //每次要舍去二进制数的最后一位}return t;
}

这就是原理是不是很简单呢（qwq）

复杂度

也许你会疑惑明明步骤变多了怎么会快了呢？这只是你的直观感觉，代码是变长了，但次数确确实实变少了，我们来看上面的代码，复杂度主要就在于循环上，循环的条件是b!=0，而每次不都要除以2，设循环次数为x，那么2^{x=b，x=log(2,b)，循环里面运算次数最多为3次，那么复杂度最大就是3log(2,N)，3是常数，当数值很大时，可以省略，复杂度为log(2,N)，那么假如算2}10000，常规需要10000次运算，而快速幂只需要14*3次运算，是不是很神奇呢？

应用

学习了这个算法有什么用呢？实际上快速幂是一个非常常用的算法，它经常与其他算法一起混用，一般来说快速幂适用于求一个指数非常高的数对某个数的余数，例如：题目：
现在星期日，问：再过2^10000天后星期几？学习了快速幂这种题就是送分题了，每次对7取余就行了

题目

附上链接，有兴趣的小伙伴可以前往相关网站做一下

Fermat's theorem states that for any prime number p and for any integer a > 1, ap = a (mod p). That is, if we raise a to the pth power and divide by p, the remainder is a. Some (but not very many) non-prime values of p, known as base-a pseudoprimes, have this property for some a. (And some, known as Carmichael Numbers, are base-a pseudoprimes for all a.)Given 2 < p ≤ 1000000000 and 1 < a < p, determine whether or not p is a base-a pseudoprime.

Input

Input contains several test cases followed by a line containing "0 0". Each test case consists of a line containing p and a.

Output

For each test case, output "yes" if p is a base-a pseudoprime; otherwise output "no".

Sample Input

Sample Output

no
no
yes
no
yes
yes

AC代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
long long p(long long a,long long b){long long t,y,n=b;t=1; y=a;while (b!=0){if (b&1==1) t=t*y%n;y=y*y%n;b=b>>1;}	return t;
}
int main()
{long long m,n;while(scanf("%lld %lld",&m,&n)!=EOF){if(m==0&&n==0) break;int flag=0;for(int i=2;i*i<=m;i++){if(m%i==0){flag=1;break;}}if(flag==0) cout<<"no"<<endl;else{if(p(n,m)==n) cout<<"yes"<<endl;else cout<<"no"<<endl;}}
}

地址：=3641

Rightmost Digit

Given a positive integer N, you should output the most right digit of N^N.

Input

The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case contains a single positive integer N(1<=N<=1,000,000,000).

Output
For each test case, you should output the rightmost digit of N^N.
Sample Input

2
3
4

Sample Output

7
6

Hint

In the first case, 3 * 3 * 3 = 27, so the rightmost digit is 7.
In the second case, 4 * 4 * 4 * 4 = 256, so the rightmost digit is 6.

AC代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
long long p(long long a){long long t,y;t=1; y=a;while(a!=0){if (a&1==1) t=t*y%10;y=y*y%10; a=a>>1;}return t;
}
int main()
{int t;cin>>t;while(t--){long long n;scanf("%lld",&n);cout<<p(n)<<endl;}
}

地址：.php?pid=1061

小蒜想知道：假设今天是星期日，那么过 aba^bab 天之后是星期几？

输入格式

两个正整数 aaa，bbb，中间用单个空格隔开。0<a≤100,0<b≤100000 < a \le 100, 0 < b \le 100000<a≤100,0<b≤10000。

输出格式

一个字符串，代表过 aba^bab 天之后是星期几。

其中，Monday 是星期一，Tuesday 是星期二，Wednesday 是星期三，Thursday 是星期四，Friday 是星期五，Saturday 是星期六，Sunday 是星期日。

输出时每行末尾的多余空格，不影响答案正确性

样例输入

3 2000

样例输出

Tuesday

AC代码

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
using namespace std;
typedef long long ll;
ll p(ll a,ll b){int t,y;t=1; y=a;while (b!=0){if (b&1==1) t=t*y%7;y=y*y%7; b=b>>1;}return t;
}
int main()
{int a,b;cin>>a>>b;switch(p(a,b)){case 1: printf("Monday\n");break;case 2: printf("Tuesday\n");break;case 3: printf("Wednesday\n");break;case 4: printf("Thursday\n");break;case 5: printf("Friday\n");break;case 6: printf("Saturday \n");break;case 0: printf("Sunday\n");break;}
}

地址：