第二次周赛G题（HDU-1061）

朱雀 2024-02-19 15:03 53阅读 0赞

问题链接：[https://vjudge.net/problem/HDU-1061][https_vjudge.net_problem_HDU-1061]

问题简述：求n的n次方的个位数。

Get：可以用快速幂，也可以找规律。

方法一：找规律  
相关链接：[https://blog.csdn.net/feynman1999/article/details/69388463][https_blog.csdn.net_feynman1999_article_details_69388463]  
[https://blog.csdn.net/yanqianglifei/article/details/77738732][https_blog.csdn.net_yanqianglifei_article_details_77738732]  
（大佬们都讲得很详细，我就不写了）

AC代码：（链接里用的是小循环，这里我用的是大循环(以20为一个周期)）

#include <iostream>
    using namespace std;
    int main()
    {
        
    	int T,N,a[21] = {
         0,1,4,7,6,5,6,3,6,9,0,1,6,3,6,5,6,7,4,9,0 };
    	cin >> T;
    	while (T--)
    	{
        
    		cin >> N;
    		cout << a[N % 20] << endl;
    	}
    }

方法二：快速幂  
相关链接：[https://blog.csdn.net/whjkm/article/details/42803805][https_blog.csdn.net_whjkm_article_details_42803805]

代码：

#include <iostream>
    using namespace std;
    int k(long long a, long long b, long long c)
    {
        
    	int cnt = 1;
    	a = a % c;
    	while (b)
    	{
        
    		if (b % 2)
    		{
        
    			cnt = cnt * a%c;
    		}
    		b = b / 2;
    		a = a * a%c;
    	}
    	return cnt;
    }
    int main()
    {
        
    	int n,a;
    	cin >> n;
    	while (n--)
    	{
        
    		cin >> a;
    		int s = k(a, a, 10);
    		cout << s << endl;
    	}
    }

[https_vjudge.net_problem_HDU-1061]: https://vjudge.net/problem/HDU-1061
[https_blog.csdn.net_feynman1999_article_details_69388463]: https://blog.csdn.net/feynman1999/article/details/69388463
[https_blog.csdn.net_yanqianglifei_article_details_77738732]: https://blog.csdn.net/yanqianglifei/article/details/77738732
[https_blog.csdn.net_whjkm_article_details_42803805]: https://blog.csdn.net/whjkm/article/details/42803805