N的N次方的个位数、暴力打表、快速幂取模

N的N次方取个位数是什么

暴力打表就是用比较小的范围看看有什么规律 比如这道题算出50以内

 1 for(int i=1;i<50;i++)
 2 {
 3             int sum =1;
 4             for(int j=1;j<=i;j++) {
 5                 sum*=i;
 6                 if(sum>10)
 7                     sum%=10;
 8             }
 9             System.out.print(sum);
10 }

结果：1476563690163656749014765636901636567490147656369

可发现每20就循环

所以可以直接弄一个数组存起来就好了

1 while(n-->0)
2 {
3             int a[]= {1,4,7,6,5,6,3,6,9,0,1,6,3,6,5,6,7,4,9,0};
4             int b=cin.nextInt();
5             int c = (b-1)%20;     //要b-1 数组下标从0开始
6             System.out.println(a[c]);
7 }

这道题也可以找出规律：

 1        /*
 2          1的所有次方都是1
 3          0的所有次方都是0
 4          5的所有次方都是5
 5          6的所有次方都是6
 6          2^1=2 2^2=4 2^3=8 2^4=6(四个一循环)
 7          3^1=3 3^2=9 3^3=7 3^4=1(四个一循环)
 8          7^1=7 7^2=9 7^3=3 7^4=1(四个一循环)
 9          4^1=4 4^2=6(两个一循环)
10          8^1=8 8^2=4(两个一循环)
11          9^1=9 9^2=1(两个一循环)
12          刚好除尽一个循环余数为0 下标对应为0  所以放在下边为0的位置
13          */
14          int a[][] = {{0},{1},{6,2,4,8},{1,3,9,7},{6,4},{5},{6},{1,7,9,3,},{6,8,4,2},{1,9}};
15  
16          while(n-->0) {
17              int b= cin.nextInt();
18              int c=b%10;
19              if(c==0||c==1||c==5||c==6) {
20                  System.out.println(c);
21              }else if(c==4||c==9)
22                  System.out.println(a[c][b&2]);
23              else
24                  System.out.println(a[c][b%4]);
25          }

取模运算：

    (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）

根据（3）可知道积的取模等于取模的积再取模、某个因子取模之后相乘再取模保持余数不变。
所以这道题可以这么算

1 int s=1;
2 n=n%10;
3 for(i=0;i<n;i++){
4     s=(s*n)%m;//本来是s=s*n  但是还有可能内存溢出  根据某个因子取模之后相乘再取模保持余数不变 所以在这里可以多取一次模
5 }
6 s=s%m;

但是这里的时间复杂度还是O（n）

快速取模的原理：

N的N次方的个位数、暴力打表、快速幂取模

根据这个思路虽然变成了O（n/2），但是可以发现k的b/2次方又可以变成L的b/4次方（L=k的平方）一直迭代下去，所以就有了快速幂取模的方法了如下所示：

 1 //方法：快速幂取模
 2          while(n-->0) {
 3              int a=cin.nextInt();
 4              System.out.println(PowerMod(a, a, 10));
 5          }
 6  
 7      }
 8      public static long PowerMod(int a, int b, int c){  
 9          long  ans = 1;
10          a = a % c;
11          while(b>0) {  
12              if(b % 2 == 1)
13                  ans = (ans * a) % c;
14              b = b/2;       这是除于2  如果是偶数倒数第二次b为1  然后ans还是会变化
15              a = (a * a) % c;
16         
17          return ans;
18 
19   }

这里时间复杂度是O（logN）

N的N次方的个位数、暴力打表、快速幂取模

相关推荐