一道趣味算法題（數(shù)學(xué)題，可以編程求解）。

emacsnw

選一個(gè)不超過(guò)一千萬(wàn)的自然數(shù) n，使它的一百萬(wàn)次方 (也就是說(shuō) n^1000000)的前四位各不相同。

koolcoy

是后四位就easy得多, 前四位有點(diǎn)麻煩.

cjaizss

so BT,誰(shuí)出的題目？^_^

yg

只算4位應(yīng)該沒(méi)啥繁的，log一下就行了

局外人

要列出全部解嗎？沒(méi)想到比窮搜更好的辦法。

12 就是一個(gè)解

12^1000000 ~ 1.762169275684230318197167758 E1079181


4 是最小解

4^1000000 ~ 9.802299377069567415894016537 E602059

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

emacsnw

原帖由 局外人 于 2007-5-2 08:33 發(fā)表
要列出全部解嗎？沒(méi)想到比窮搜更好的辦法。

12 就是一個(gè)解

12^1000000 ~ 1.762169275684230318197167758 E1079181


4 是最小解

4^1000000 ~ 9.802299377069567415894016537 E602059

你這幾個(gè)都是正確的，不知道你是如何求解？

emacsnw

原帖由 GKL 于 2007-5-2 05:18 發(fā)表
需要找出所有的解嗎？

窮舉估計(jì)得很長(zhǎng)時(shí)間。。

只需要找出一個(gè)解即可，如果用數(shù)學(xué)方法當(dāng)然最好，編程的話加個(gè)要求，除了math.h里面的函數(shù)，第三方的庫(kù)不能用，比如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. }
    

復(fù)制代碼

1. 
   
2. 9.802299e+03
   

復(fù)制代碼

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

局外人

n^1000000 如果有 d 個(gè)十進(jìn)制位， 則 n^1000000/10^(d-4)  的整數(shù)部分就是前 4 位

用 log 和 pow 計(jì)算 d 和上面的這個(gè)值就可以了.

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