HDU 1097 A hard puzzle(快速幂模板||规律)

忘是亡心i 2021-11-02 06:30 180阅读 0赞

**A hard puzzle**

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)**  
**Total Submission(s): 14975    Accepted Submission(s): 5314**  
  
**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**

**Author**

eddy

**Recommend**

JGShinin

方法一：找规律

解题报告：此题是一个找规律的题目，结果至于尾数有关，而尾数从2到9的几次方有个规律，尾数是1,5，6的循环规律是1。尾数是4,9的循环规律是2，尾数是2,3，7,8，的循环规律是4.所以最大的公倍数是4；

方法一： 找规律：

代码如下：

#include<iostream>
    #include <cstdio>
    int main()
    {
        
    int a[4],m,n;
    while(scanf("%d%d",&m,&n)!=EOF)
        {
        
            a[1]=m%10;
            a[2]=(a[1]*a[1])%10;
            a[3]=(a[1]*a[2])%10;
            a[0]=(a[1]*a[3])%10;
            n=n%4;
            printf("%d\n",a[n]);
        }
    return 0;
    }

方法二：快速幂模

代码如下：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    //m^n  % k 的快速幂：
    __int64 Expmod(__int64 m,__int64 n,int k)
    {
        
        __int64 b=1;
    while(n>0)
        {
        
    if(n%2==1)
            {
        
                b=(b*m)%k;
            }
            n=n/2;
            m=(m*m)%k;
        }
    return b;
    }
    int main()
    {
        
        __int64 x,y;
    while(scanf("%I64d%I64d",&x,&y)!=EOF)
        {
        
            printf("%I64d\n",Expmod(x,y,10));
        }
    return 0;
    }

转载于:https://www.cnblogs.com/lidaojian/archive/2011/11/26/2264657.html