/ hdoj

hdoj-1060 ]Leftmost Digit 左值

题目大意:

1.第一行输入一个整数T代表接下来有T组测试数据。
2.接下来的T行,每行输入一个整数(1<=N<=1,000,000,000)。
3.输出结果为N^N(N的N次方)最左边的那一位数(即最高位)。
4.注意:每行输出一个结果。

解题思路:

1.令M = N^N
2.两边取对数,log10M = Nlog10N,得到M = 10^(Nlog10N)
3.令N^(N*log10N) = a(整数部分) + b(小数部分),所以M = 10^(a+b) = 10^a *10^b,由于10的整数次幂的最高位必定是1,所以M的最高位只需考虑10^b
4.最后对10^b取整,输出取整的这个数就行了。(因为0<=b<1,所以1<=10^b<=10对其取整,那么的到的就是一个个位,也就是所求的数)。

需要注意的地方:

关于取整:可以用强制类型转换(int)10^b,也可以用floor函数floor(10^b),但要注意的问题是floor函数是double型的,若用floor函数,则在输出时要用"%.0lfn",(有关floor函数和ceil函数,详见http://baike.baidu.com/view/2873705.htm)

代码

// hdoj_1060 Leftmost Digit
// 0MS	236K	345 B	GCC

#include <stdio.h>
#include <math.h>
int main(void)
{
    int n, i, ncase;
	long long x;
	scanf("%d", &ncase);
    for(i = 0; i < ncase; i ++)
    {
        scanf("%ld", &n);
        double m = n * log10((double)n);
        double g = m - (long long)m;
        g = pow(10.0, g);
        printf("%dn", (int)g);
    }
	return 0;
}

总结:
开始写了一个程序提交了几次Time Limit Exceeded
数太大了,求n^n花费时间太长……
看了别人的代码之后才明白
求log10之后计算会更简单
这个题目有点思想,不算水题,只能说找到方法后就很简单。

log10N^N = N*log10N = M = a.b(a是整数部分,0.b是小数部分)
所以10^M = 10^a.b = N^N(即N^N为a位数)
10^b向下取整即为首位数
举个例子:3^3=27, 3log3 = 1.431364, 10^0.431364 = 2.70000……
此题还是要学会观察,并熟悉对数