最开始自己用计算器发现每四个循环一次，写如下代码：
/*HOJ1604 二分*/
#include<iostream>
#include <iostream>
#include<stdio.h>
#include <iomanip>
#include <string.h>
#include <math.h>
#include <iostream>
using namespace std;
int main()
{
long long n,i,t,a[4],b[4],y;
cin >> t;
while(t--)
{
cin >> n;
if(n==0) cout << 0 << endl;
if(n==1) cout << 1<< endl;
if(n==2) cout << 4 << endl;
if(n==3) cout << 7 << endl;
if(n==4) cout << 6 << endl;
if(n>4)
{
y=(n-1)%4;
a[0]=n;
for(i=1; i<=3; i++)
{
a[i]=a[i-1]*n;
//cout << a[i] <<endl;
}
for(i=0; i<4; i++)
{
b[i]=a[i];
//cout << b[i] <<endl;
}
//cout << y << endl;
if(y!=0)cout << b[y] << endl;
else cout << b[3] << endl;
}
}
return 0;
}
但是是wa，后来输入几个较大的数之后出现负数，所以发现是数据范围小啦，改为long long 但是输入较大的数据之后还是会越界，百度之后发现思路是这样的：
（n mod 10）^n righest ==n; #include <iostream> #include<stdio.h> #include <iomanip> #include <string.h> #include <math.h> #include <iostream> using namespace std; int main() { int n,i; int s,t; int a[10][4]={{0,0,0,0},{1,1,1,1},{6,2,4,8},{1,3,9,7},{6,4,6,4},{5,5,5,5},{6,6,6,6},{1,7,9,3},{6,8,4,2},{1,9,1,9}}; //分别是 n^4 n^1 n^2 n^3 (0<=n<=9) (n^5 mod 10 == n) cin >> t; while(t--) { cin >> n; if(n) cout << a[n][n%4]<< endl; else cout << 1 << endl; } return 0; }
ac~~~~~~~~~~~~~~~~`
acm吧有人给出这样的思路：
不知道你那个规律多半是错的。。估计大数据过不了
有一个常规的方法是利用对数
可以令n^n=A*10^L A的范围是(0,1),L是n^n计算出来后的位数
L的计算方法是对n^n取10的对数在取整，即L=[nlgn]
那么n^n=A*10^([nlgn])
这样之后，两边同时对10取对数
得到:nlgn=lgA+[nlgn]
于是乎lgA=nlgn-[nlgn]
A=10^(nlgn-[nlgn])
由于A是(0,1)，此时只需计算[A*10]即可。（有一些小bug需要你自己找一下，我就不多说了）
有一个常规的方法是利用对数
可以令n^n=A*10^L A的范围是(0,1),L是n^n计算出来后的位数
L的计算方法是对n^n取10的对数在取整，即L=[nlgn]
那么n^n=A*10^([nlgn])
这样之后，两边同时对10取对数
得到:nlgn=lgA+[nlgn]
于是乎lgA=nlgn-[nlgn]
A=10^(nlgn-[nlgn])
由于A是(0,1)，此时只需计算[A*10]即可。（有一些小bug需要你自己找一下，我就不多说了）
没有写过：应该是对的！