首页 > 代码库 > A hard puzzle

A hard puzzle

2024-08-03 19:15:01   219人阅读

A hard puzzle

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 30832 Accepted Submission(s): 11063


Problem Description
lcy gives a hard puzzle to feng5166,lwg,JGShining and Ignatius: gave a and b,how to know the a^b.everybody objects to this BT problem,so lcy makes the problem easier than begin.
this puzzle describes that: gave a and b,how to know the a^b‘s the last digit number.But everybody is too lazy to slove this problem,so they remit to you who is wise.

Input
There are mutiple test cases. Each test cases consists of two numbers a and b(0<a,b<=2^30)

Output
For each test case, you should output the a^b‘s last digit number.

Sample Input
7 66
8 800

Sample Output
9
6




解决方案：
假设a=38,b=2,那么结果应为(a*a)%10=(38*38)%10=[(38%10)*(38%10)]%10=4;
假设a=27,b=2,那么结果应为(a*a)%10=(27*27)%10=[(27%10)*(27%10)]%10=9;

.......
可以看出，(a^b)%10=(a*a*a......*a)%10=[(a%10)*(a%10)*(a%10)*.....(a%10)]%10;
那么就可以使用(b-1)次循环，求出(a^b)%10的结果，但这样时间复杂度就是O（b-1)，提交给OJ后，会提出超时的警告。
所以需要一个时间复杂度更低的程序。
正整数a不管多大，都是十进制数，所以a%10的结果必然是0-9中的一个数。
0^n=0，那么只要以0结尾的数，该数的n次方的个位数还是0。
1^n=1，那么只要以1结尾的数，该数的n次方的个位数还是1。

同样以5结尾的数也是如此。那其它的数字又不一样，最后得出下列这张表：


从红色的框中可以看出：0-9中任何一个数字，其n次方后的个位数是有规律的。每4次一个循环。所以只要先前列一个数组，将其
保存，就可以直接找到对应的数组元素就是其(a^b%10)的值，这样时间复杂度为0（1）；
#include<iostream>
using namespace std;
int main()
{
    int a,b,col,row;
    int result[4][10]=
    {
        {0,1,6,1,6,5,6,1,6,1},
        {0,1,2,3,4,5,6,7,8,9},
        {0,1,4,9,6,5,6,9,4,1},
        {0,1,8,7,4,5,6,3,2,9}
    };
    while(cin>>a>>b)
    {
        row=b%4;//对周期4取余，其余数为0,1,2,3 
        col=a%10;


        cout<<result[row][col]<<endl;
    }
    return 0;
}

A hard puzzle


联系
我们