C - Rightmost Digit
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Submit Status Practice HDU 1061
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).
Output
For each test case, you should output the rightmost digit of N^N.
Sample Input
2
3
4
Sample Output
7
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.
Difficulty:这题一开始想直接算出那个数，然后再取余数，后来发现这个数太大会超出计算机范围（爆了）。这时就需要用到一定的数学知识：在乘法中最后一位数，只取决于两个数的最后一位数。列如129*19的两个数的最后一位数取决于9*9 =81即129*19最后一位数为1.所以要边计算边取余数。
#include<cstdio>
#include<cstring>
using namespace std;
int t,a,b;
long long n,k,ans;
int main()
{
scanf("%d",&t);
while(t--)
{ a=b=k=0;ans=1;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
a=n%10;
ans*=a;
ans=ans%10;
}
printf("%d\n",ans);
}
return 0;
}
后来发现N给的10的9次方这么大，如果for循环肯定会TLE。这时又要用快速幂来优化：快速幂：
也就是说：a^8=(a^4)^2，这样算一次a^4就等于算了两次a^4了~所以这里我用到递归，a^4=(a^2)^2，a^2=(a^1)^2；那么知道a即可求出。
#include<cstdio>
#include<cstring>
using namespace std;
int t,a,b;
long long n,k,ans,y;
long long pow(long long k,long long n)
{if(k==1)
return n%10;
if(k%2==1)//快速幂
{k=(k-1)/2;
y=pow(k,n);//递归
ans=y*y*n%10;
ans=ans%10;//边计算边取余数
return ans;}
else
{k=k/2;
y=pow(k,n);
ans=y*y;
ans=ans%10;
return ans;
}
}
int main()
{
scanf("%d",&t);
while(t--)
{ a=b=y=0;ans=1;
scanf("%d",&n);
k=n;
printf("%lld\n",pow(k,n));
}
return 0Way 2:位运算，将n看作是二进制，例如9=111。即N的9次方等于N的2^2次方乘N的2^1次方乘2^0次方。
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int t,k,b;
long long n;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%lld",&n);
k=1;
b=n%10;
while(n)
{
if(n%2==1)
{
k*=b;
k=k%10;
}
b*=b;//2进制进位。可以自己手算。
b=b%10;
n=n/2;
//printf("%d\n",k);
}
printf("%d\n",k);
}
return 0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。