一道趣味算法题（数学题，可以编程求解）。

emacsnw

选一个不超过一千万的自然数 n，使它的一百万次方 (也就是说 n^1000000)的前四位各不相同。

koolcoy

是后四位就easy得多, 前四位有点麻烦.

cjaizss

so BT,谁出的题目？^_^

yg

只算4位应该没啥繁的，log一下就行了

局外人

要列出全部解吗？没想到比穷搜更好的办法。

12 就是一个解

12^1000000 ~ 1.762169275684230318197167758 E1079181


4 是最小解

4^1000000 ~ 9.802299377069567415894016537 E602059

[ 本帖最后由 局外人 于 2007-5-3 00:35 编辑 ]

emacsnw

原帖由 局外人 于 2007-5-2 08:33 发表
要列出全部解吗？没想到比穷搜更好的办法。

12 就是一个解

12^1000000 ~ 1.762169275684230318197167758 E1079181


4 是最小解

4^1000000 ~ 9.802299377069567415894016537 E602059

你这几个都是正确的，不知道你是如何求解？

emacsnw

原帖由 GKL 于 2007-5-2 05:18 发表
需要找出所有的解吗？

穷举估计得很长时间。。

只需要找出一个解即可，如果用数学方法当然最好，编程的话加个要求，除了math.h里面的函数，第三方的库不能用，比如GMP.

局外人

用 log 和 pow

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <math.h>
   
5. 
   
6. 
   
7. int
   
8. main (int argc, char **argv)
   
9. {
   
10.         unsigned long digits;
    
11.        
    
12.         double N, M, r;
    
13.         unsigned long m = 1000000UL;
    
14. 
    
15.         N=4;
    
16.         M= log(N)*1000000/log(10);
    
17.         r=pow(10, M-ceil(M)+4);       
    
18.         printf ("%e\n", r);
    
19. }
    

复制代码

1. 
   
2. 9.802299e+03
   

复制代码

[ 本帖最后由 局外人 于 2007-5-3 10:13 编辑 ]

局外人

n^1000000 如果有 d 个十进制位， 则 n^1000000/10^(d-4)  的整数部分就是前 4 位

用 log 和 pow 计算 d 和上面的这个值就可以了.

[ 本帖最后由 局外人 于 2007-5-3 10:14 编辑 ]