首页 > 代码库 > （HDU）1061 --Rightmost Digit( 最右边的数字）

（HDU）1061 --Rightmost Digit( 最右边的数字）

2024-08-25 02:47:53   218人阅读

题目链接：http://vjudge.net/problem/HDU-1061

这个题目要求出N个N相乘的个位，直接求结果肯定数据溢出。

 

其实只要每次得出一个数字保留个位和N相乘就可以了，

因为A*B=C，对于个位而言，A（个位）*B（个位）=C（个位）始终成立。

1<=N<=1,000,000,000，这样写还是TLE了。

技术分享 
 1     #include <iostream>
 2     #include <cstdio>
 3     #include <cstring>
 4     using namespace std;
 5 
 6     int main()
 7     {
 8         int t,n,i;
 9         scanf("%d",&t);
10         while(t--)
11         {
12             scanf("%d",&n);
13             int ans=1;
14             for(i=1;i<=n;i++)
15             {
16                 ans*=n;
17                 ans%=10;
18             }
19             printf("%d\n",ans);
20         }
21         return 0;
22     }
View Code

 

来换一个思路，沿用上面的思路，我们来找一个个位周期：

0：0 0 0 0 0 0 0 0 0 0

1：1 1 1 1 1 1 1 1 1 1

2：2 4 8 6 2 4 8 6 2 4

3：3 9 7 1 3 9 7 1 3 9

4：4 6 4 6 4 6 4 6 4 6

5：5 5 5 5 5 5 5 5 5 5

6：6 6 6 6 6 6 6 6 6 6

7：7 9 3 1 7 9 3 1 7 9

8：8 4 2 6 8 4 2 6 8 4

9：9 1 9 1 9 1 9 1 9 1

有一个普遍规律，周期为4。

 

技术分享 
 1     #include <iostream>
 2     #include <cstdio>
 3     #include <cstring>
 4     using namespace std;
 5 
 6     int main()
 7     {
 8         int t,n,temp,ans[4];
 9         scanf("%d",&t);
10         while(t--)
11         {
12             scanf("%d",&n);
13             temp=n;
14             temp%=10;
15             ans[1]=temp;
16             ans[2]=(ans[1]*temp)%10;
17             ans[3]=(ans[2]*temp)%10;
18             ans[0]=(ans[3]*temp)%10;
19             printf("%d\n",ans[n%=4]);
20         }
21         return 0;
22     }
View Code

 

（HDU）1061 --Rightmost Digit( 最右边的数字）


联系
我们