Leftmost Digit

Leftmost Digit

    Time Limit: 1000 ms 

    Memory Limit: 65535 kB 

    Description

     Given a positive integer N, you should output the leftmost 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 leftmost digit of N^N. 

Sample Input

2

3

4

Sample Output

2

2

Source

對于任何一個數我們可以寫成這樣的形式：a*10^n

同樣對于n^n我們可以寫成10^m*a，即n^n = a*10^m，我們要求的n^n的Leftmost位即最高位，即a的最高位，即整數位。

兩邊同時取對數即nlogn = loga + m，即a要等于nlogn的小數部分。

那麼temp=loga = nlogn-(long long)nlogn,

是以a = 10^loga=10^temp,即為所求。

這裡能得到啟發：對于很大的數的處理，取對數往往能收到很不錯的效果。

#include <cstdio>
 #include <cmath>
 
 int main()
 {
 	int t, n;
 	FILE * fin, * fout;
 	fin = fopen("1.std.in", "r");
 	fout = fopen("1.std.out", "w");
 	fscanf(fin, "%d", &t);
 	while ( t-- )
 	{
 		fscanf(fin, "%d", &n);
 		double temp = n * log10(1.0 * n);
 		double a = temp - (long long)temp;
 		a = pow(10.0, a);
 		fprintf(fout, "%d\n", (long long)a);
 	}
 	return 0;
 }