HDU Rightmost Digit
2024-09-02 06:03:11
Rightmost Digit
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Description
Given a positive integer N, you should output the most right digit of N^N.
Input
The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case contains a single positive integer N(1<=N<=1,000,000,000).
Each test case contains a single positive integer N(1<=N<=1,000,000,000).
Output
For each test case, you should output the rightmost digit of N^N.
Sample Input
2
3
4
3
4
Sample Output
7
6
6
Hint
In the first case, 3 * 3 * 3 = 27, so the rightmost digit is 7.
In the second case, 4 * 4 * 4 * 4 = 256, so the rightmost digit is 6.
普通的算法会超时,数据量比较大,到1亿了
优化算法,分治思想.
例如:( 5^5)%10 = ((5^2)^2*5)%10;
这个过程中要取余 !
还有一种思想利用乘方尾数周期性的关系!
#include <stdio.h>
#include <string.h> int mod(int a, int n)
{
long long x;
long long ans;
if(n==1||n==0)
return n==0?1:a; x = mod(a, n/2);
ans = x * x % 10; if(n%2==1)
ans=ans*a%10 ;
return (int)ans;
} int main()
{
int t;
int a;
int dd;
scanf("%d", &t);
while(t--)
{
scanf("%d", &a );
dd = mod(a, a);
printf("%d\n", dd );
}
return 0;
}
最新文章
- [原创]java WEB学习笔记103:Spring学习---Spring Bean配置:基于注解的方式(基于注解配置bean,基于注解来装配bean的属性)
- [Qt系列] 何处下载,如何安装!
- 去掉DLL can move
- RaisingStudio.PackageManager 发布 1.0版
- Windows Server 2016软件定义存储:Storage Spaces Direct的关键特性
- asp.net mvc 接入最新支付宝支付+退款 alipay-sdk-NET-20170615110549
- 谈谈 ANR 之 Service 超时
- 美化ubuntu18.04,并安装搜狗输入法
- Lucene 07 - 对Lucene的索引库进行增删改查
- Python并发编程之IO模型
- Unity 个人用过的地面检测方案总结
- 关于dom&;bom
- Wordpress 更新时 不输入ftp相关信息的方法
- 11. pt-heartbeat
- List元素删除不会导致越界但有问题的写法
- CPP_template
- 能ping通外网dns但不能上网一例
- 使用递归计算n的阶乘n!
- PHP包管理
- Oracle DB 移动数据