| Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) |
| Total Submission(s): 2012 Accepted Submission(s): 576 |
|
Problem 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. |
|
Author
Ignatius.L
|
两种方法来自百度知道： （1）“是指求n^n最后那位的那题？
杭电OJ1061
这个可以化简的啊~~~
(a*b)%n=((a%n)*(b%n))%n
所以呢~
完全可以乘一次n，再求一次10的余数。然后对余数进行下一次的次方操作~
若n太大，则可用二进制优化，将n看作是二进制，例如8=1000
然后，n^8=(n^4)^2，这样算一次n^4就等于算了两次n^4了~
附上代码~”
#include<iostream>
using namespace std;
int rightD(int n)
{
int ans=1;
int a=n,b=n;
a%=10;
while(b)
{
if(b%2==1)
{
ans*=a;
ans%=10;
}
b/=2;
a*=a;
a%=10;
}
return ans;
}
int main()
{
int t,n;
cin>>t;
while(t--)
{
cin>>n;
cout<<rightD(n)<<endl;
}
return 0;
} （2） 看最后一位数字的次方 1的所有次方都是1 0的所有次方都是0 5的所有次方都是5 6的所有次方都是6 2^1=2 2^2=4 2^3=8 2^4=6(四个一循环) 3^1=3 3^2=9 3^3=7 3^4=1(四个一循环) 7^1=7 7^2=9 7^3=3 7^4=1(四个一循环) 4^1=4 4^2=6(两个一循环) 8^1=8 8^2=4(两个一循环) 9^1=9 9^2=1(两个一循环) 故程序如下： #include<stdio.h> main() { int n,cas,m; scanf("%d",&cas); while(cas--) { scanf("%d",&n); m=n%10; if(m==0||m==1||m==5||m==6) printf("%d\n",m); if(m==2) { if (n%4==1) printf("2\n"); if (n%4==2) printf("4\n"); if (n%4==3) printf("8\n"); if (n%4==0) printf("6\n"); } if(m==3) { if (n%4==1) printf("3\n"); if (n%4==2) printf("9\n"); if (n%4==3) printf("7\n"); if (n%4==0) printf("1\n"); } if(m==7) { if (n%4==1) printf("7\n"); if (n%4==2) printf("9\n"); if (n%4==3) printf("3\n"); if (n%4==0) printf("1\n"); } if(m==8) { if (n%4==1) printf("8\n"); if (n%4==2) printf("4\n"); if (n%4==3) printf("2\n"); if (n%4==0) printf("6\n"); } if (m==4) { if (n%2==1) printf("4\n"); if (n%2==0) printf("6\n"); } if (m==9) { if (n%2==1) printf("9\n"); if (n%2==0) printf("1\n"); } } }
是指求n^n最后那位的那题？杭电OJ1061这个可以化简的啊~~~(a*b)%n=((a%n)*(b%n))%n所以呢~完全可以乘一次n，再求一次10的余数。然后对余数进行下一次的次方操作~若n太大，则可用二进制优化，将n看作是二进制，例如8=1000然后，n^8=(n^4)^2，这样算一次n^4就等于算了两次n^4了~附上代码~#include<iostream>using namespace std;
int rightD(int n){int ans=1;int a=n,b=n;a%=10;while(b){if(b%2==1){ans*=a;ans%=10;}b/=2;a*=a;a%=10;}return ans;}int main(){int t,n;cin>>t;while(t--){cin>>n;cout<<rightD(n)<<endl;}return 0;}