小明解密码
题目大意
让你计算n^m的个位（有t组数据）
样例输入
2
3 4
4 5
样例输出
1
4
数据范围限制
对于30％的数据，1≤t≤20，1≤n,m≤8
对于100％的数据，1≤t≤1000，1≤n,m≤10^10
解题方法
这题其实有两种方法，一种是运用个位的规律直接得出结果（这里我就不详细说明了），另一种是我们一想就可以想到的“幂”，但从数据m<= 1 0 10 10^{10} 1010可以得知，我们要用快速幂（注意输入要用long long，因为 1 0 10 10^{10} 1010>2147483647）
快速幂：
就是将一个幂的指数分成两份如： n 10 n^{10} n10= n 5 n^{5} n5× n 5 n^{5} n5（因为都是10个n相乘），但当指数为奇数时，就要多成一个n，如： n 11 n^{11} n11= n 5 n^{5} n5× n 5 n^{5} n5×n
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30#include<cstdio> #include<iostream> using namespace std; int t; long long n,m,ans; void ksm(long long x) { if (x==1)//判断是否为一次方 { ans=n;//一次方即为本身 return; } ksm(x/2);//指数除以2 long long d=1; if (x&1) d=n;//如果x为奇数，多乘一个n ans=(ans*ans*d)%10;//相乘 } int main() { scanf("%d",&t);//数据的组数 for (int i=1;i<=t;i++) { scanf("%lld %lld",&n,&m); n%=10;//求各位 ksm(m);//快速幂 printf("%lldn",ans);//输出 } return 0; }
最后
以上就是欣慰导师最近收集整理的关于【快速幂】小明解密码 （jzoj 2146）小明解密码的全部内容，更多相关【快速幂】小明解密码内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复