开发者社区人工智能文章正文

51Nod 1004 n^n的末位数字(日常复习快速幂，莫名的有毒，卡mod值)

2017-07-02 1087

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 1004 n^n的末位数字题目来源： Author Ignatius.L (Hdu 1061) 基准时间限制：1 秒空间限制：131072 KB 分值: 5 难度：1级算法题给出一个整数N，输出N^N（N的N次方）的十进制表示的末位数字。

1004 n^n的末位数字

题目来源： Author Ignatius.L (Hdu 1061)

基准时间限制：1 秒空间限制：131072 KB 分值: 5

难度：1级算法题

给出一个整数N，输出N^N（N的N次方）的十进制表示的末位数字。

Input

一个数N（1 <= N <= 10^9）

Output

输出N^N的末位数字

Input示例

Output示例

题目链接： http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1004

分析：快速幂第二题，莫名的奇妙，mod的值卡在1e7，我也是无语了，写了个1e9+7，样例都过不了，写个1e60，连续WA，这肯定是在卡数据！
下面给出AC代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const ll mod=1e7;
 5 ll qpow(ll x,ll p)
 6 {
 7     ll ret=1;
 8     for(;p;p>>=1,x=x*x%mod)
 9     {
10         if(p&1)
11             ret=ret*x%mod;
12     }
13     return ret;
14 }
15 int main()
16 {
17     ll x;
18     cin>>x;
19     ll p=x;
20     ll ans=qpow(x,p);
21     cout<<ans%10<<endl;
22 }