hdu 1060 Leftmost Digit

缘起

给你一个正整数N，求N^N 最高位.

分析

题意很裸

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
给定正整数N，您应该输出N^N的最左边的数字。

【输入】
输入包含几个测试用例。 输入的第一行是单个整数T，它是测试用例的数量。 
每个测试用例包含一个正整数N（1 <= N <= 1,000,000,000）。

【输出】
对于每个测试用例，您应该输出N^N的最左边的数字。

【样例输入】
2
3
4

【样例输出】
2
2

【限制】
Time limit 1000 ms
Memory limit 32768 kB

令 M=N^N，两边取以10为底的对数.
$$
log_{10}M = Nlog_{10}N;
$$
令 Nlog_{10}N=x+y, 其中 x是整数部分, y是小数部分, 则
$$
M=10^{x+y}=10^x*10^y
$$
而0<=y<1, 所以1<=10^y <10, 所以M的最高位其实就是 10^y的整数部分. 即问题的算法就是

1
2
1. 求出 NlogN 的小数部分y
2. 求出 10^y 的整数部分就是答案.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include "stdafx.h"

#include <stdio.h>
#include <math.h>
#define LOCAL
typedef long long LL; // 考虑N的上限,是需要使用long long的

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	LL n, tt;
	scanf("%lld", &tt);
	while(tt--)
	{
		scanf("%lld", &n);
		double t = n*log(1.0*n)/log(10.0);
		double y = t-(LL)t;
		printf("%d\n", (int)pow(10.0, y));
	}
	return 0;
}

ac情况

30151500 2019-08-07 14:00:19 Accepted 1060 0MS 1208K 371 B G++ yfsyfsyfs