Num 16: HDOJ: 题目1061 : Rightmost Digit [ 求个位数 ] [ 快速

题目：

Rightmost DigitTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 39386Accepted Submission(s): 14861

Problem Description

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

234

Sample Output

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.

刚看到题的时候就应该意识到，一定不能强行计算 N^N%10 然后输出，计算量大，，而且会数据溢出；

大数乘法在这里也不太合适，毕竟要算N次方，就算计算出来，submit 的时候也不能够保证不超时；

所以感觉到应该是有内在规律，仔细研究后发现：

在计算 N^N 的个位数的时候，个位数的数值仅与N的个位数有关；

所以可以利用计算( N%10 )^N 的个位数来代替原题；

进一步的，演算后发现1-9的N( N>0 )次方按4个数一循环；

例：3的1-9次方的个位数依次为 ( 3, 9,7,1,3,9,7,1,3) ;

所以对于次方数也可以做简化，次方为：N%4 ;

这里要注意，当N%4==0的时候N应当取4；( 否则X^0=1,只会输出1 )

通过以上的分析，我们就将问题转化为求 ( N%10 )^( N%4 )的个位数的问题了；

大大简化了计算过程，而且保证了数据一定不会溢出；

AC代码：

#include<stdio.h>#include<math.h>int main(){int t;scanf("%d",&t);while(t–){int n,num,index;scanf("%d",&n);num=n%10;index=n%4;if(index==0) index=4;printf("%d\n",(int)(pow((double)num,index))%10);}return 0;} 注意：pow函数的格式pow( double x, int index )，要学会利用类型的强制转换；

见网上也有许多人在说用快速幂的方法也可以做；

这里仅介绍快速幂算法，不推荐在这道题上使用快速幂的方法；

快速幂：

分为二分法和位运算( 位操作 )；

原理：

例如在计算 2^4 的时候，当计算过 2^2后，可以直接计算 ( 2^2 )^2即可；

1.二分法：

#include<stdio.h>int pow2(int a,int b)// a：底数 b：指数{int r=1,base=a;while(b!=0){if(b%2) r*=base; // 如果次方为奇数，r乘一个底数( 使次方变为偶数 )；base*=base;// 每计算循环一次，底数所乘的数都为上一次的平方倍，减少次数；b/=2;}return r;}int main(){int a,b;while (scanf("%d%d",&a,&b))printf("%d\n",pow2(a,b));}

2.位运算：

原理和二分法相似，只不过是通过位运算来对数据做处理的；

#include<stdio.h>int pow3(int a,int b){int r=1,base=a;while(b!=0){if(b&1)r*=base;base*=base;b>>=1;}return r;}int main(){int a,b;while (scanf("%d%d",&a,&b))printf("%d\n",pow3(a,b));}

我们也可以用计算快速幂的方法来进行余数的计算( 求个位数即对10取余 )：

这里用到的方法为：

快速幂取模算法：

利用离散数学之中所讲的知识，我们有公式：

( a^b ) mod c=( a mod c )^b mod c ;

通过数学知识，我们可化简此等式有( 可循环[ 递归 ]计算 )：

奇数时：(a mod c) * ( a^2 mod c)^( b/2 ) mod c ;

偶数时： a^2 mod c)^( b/2 ) mod c ;

哪里有意志存在，哪里就会有出路。

相关文章：

你感兴趣的文章：

标签云：