HTML5 Firefox nginx java apache mysql linux命令 wordpress linux 微软 程序员 shell Android google 开源 php Ubuntu Windows Python centos

一种快速求N的N次方的个位数的算法

ACM题库有这么一道题:

求N的N次方的个位数。很简单的题目,但是如果用普通算法就会超时,因为N可能很大很大。

本文介绍自己想出的一个快速求解办法。也许也有人跟我想的一样。

先看公式:

3*3*3=27,所以答案应该是7.
4*4*4*4=256,所以答案应该是6.

最容易想到的就是连续乘N,最后按10取余数。但是肯定会超时的。

其实不难发现,做连乘的时候,个位数变化是比较有规律的。比如以6,1,0结尾的数,无论多大,自己本身的N次方的个位数还是6,1,0.

所以就想到计算一个pos指针,它可以指明个位数的变化是多大的一个循环。
对6,1,0来说,pos=1。
然后比如计算1236的1236次方,对1236取1的余数,为0.
说明只需要取得1236的个位数,就是1236的1236次方的个位数。
如果还不明白,下面以个位数为3的整数为例,说明pos指针的运作。
3*3=9
9*3=27
7*3=21
1*3=3
3*3=9

看,一个尾数为3的整数,它自己次方的尾数会在4次循环之后回到9.所以pos按此法计算。

下面是代码:

import JAVA.util.Scanner;

public class Main {
public static int pow(int x){
int a=x%10; //a是x的个位数
int y=a;
int pos=1;//pos 是指示几个循环 a会变回自己
int temp=a*a;
while(a!=temp%10){
temp*=a;
pos++;
}
int loot=(x-1)%pos;
for(int i=0;i<loot;i++){
y=y*a;
}
y=y%10;
return y;
}
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
while(n--!=0){
int x=sc.nextInt();
System.out.println(pow(x));
}
}
}

延伸阅读

评论

  1. 其实你的算法有一些过程不够清楚。请看:
    任何整数都可以表示为10a+b,其中0<=b<9,那么计算结果就是(10a+b)^(10a+b)。
    按照二相式定理,最终结果的各位数就是b^(10a+b),因为其他项都需要乘10.