找到一個範圍內的自我產品的數量

Question

問題在標題中。現在讓自我產品這個詞更加清晰。自我產品意味着數字和數字的乘積。例如：

自產品（1234）= 1234 * 1 * 2 * 3 * 4 = 29616.

我嘗試兩種方法。

蠻力

任何人的想法是將檢查1和N之間的所有組合（上界範圍的）。並檢查號碼的自我產品是否在範圍內。這對於相對較低的數字來說很理想，但考慮到範圍可能大到10^20，這就成了一個問題，因爲打印結果需要一段時間。

因式分解

另一個想法是該範圍內的因式分解的數目。如果範圍在60 000到70 000之間，當我檢查62 688時，我會得到62 688 2 * 2 * 2 * 2 * 2 * 3 * 653。現在知道653不能是一個數字，這意味着它必須在原始數字。再次，我必須結合所有因素62 688得到正確的答案，它應該輸出這一個是2612的自產品，因爲62 688 = 2612 * 2 * 6 * 1 * 2.

在兩個我面臨一個很大的問題，那就是檢查所有的組合。

P.S我發現，如果數量爲n位數那麼，如果它的一些多項自主產品比這個數字將至少有N/2位數，沒有以上n。這將使我需要檢查一點點的數字清單，但它不能解決問題。

Answer 1

所以我們說產品是由digits和number形成。

只是列舉數字（），檢查每一個置換（其中形成數字），看看它的範圍。

一個明顯的修剪時的數字和最小排列的產品比上界大，你回來。

我認爲這將是足夠快的32位整數。

Answer 2

命名：

sp(x) = Self-Product(x) = y 
Range = a to b 

注：

我會認爲你只是想計數，但擴展這個實際打印所有的數字應該不是難事。

基本思路 - 將x分割成若干數字前綴和一定數量的數字，並確定一些數字+前綴是否落入該範圍內，或者完全（增加可能性數量，易於計算），部分（檢查更長的前綴）或根本不（移動）。

請注意，任何包含0的數字x都是不允許的，因爲y = 0。

該算法可能有一些低效率，但它應該提供一個體面的起點。一種改進是應該能夠執行類似二進制搜索的過程。另一個是不重新計算最小/最大值，因爲這裏有一定的冗餘。

記號：
min(c,d) - 最小採用c數字和d的前綴（min(c,)意味着沒有前綴）
max(c,d) - 最大爲c的數字和d
range(c,d)的前綴 - 範圍從min(c,d)到max(c,d)

注意min(x,) = min(x,1) < min(x,2) < min(x,3) < ...和
max(x,) = max(x,9) > max(x,8) > max(x,7) > ...

min(c,d..e) - 設置爲c數字和從d任何前綴最小值至E
（之間min(c,d)和min(c,e)）
max(c,d..e) - 其中c位數的最大值的集合，並從d任何前綴到e
（之間max(c,d)和max(c,e)）

算法通過實施例：

我將解釋使用用於範圍的示例= 100〜200。

// check 1 digit 
min(1,): x = 1, y = 1*1 = 1 < 100 
max(1,): x = 9, y = 9*9 = 81 < 100 
    // not in range, nothing to do 

// check 2 digits 
min(2,): x = 11, y = 11*1*1 = 11 < 100 
max(2,): x = 99, y = 99*9*9 = 8019 > 200 
    // partially in range, check longer prefix 
    min(2,1): x = 11, y = 11*1*1 = 11 < 100 
    max(2,1): x = 19, y = 19*1*9 = 171 > 100 
    // partially in range, check longer prefix 
    sp(11..16) <= sp(16) = 96 < 100 
    sp(17) = 119 // in range - increment count 
    sp(18) = 144 // in range - increment count 
    sp(19) = 171 // in range - increment count 
    min(2,2): x = 21, y = 21*2*1 = 42 < 100 
    max(2,2): x = 29, y = 29*2*9 = 522 > 200 
    // partially in range, check longer prefix 
    // others outside of range, omitted for brevity 
    sp(23) = 138 // in range - increment count 
    sp(24) = 192 // in range - increment count 
    min(2,3): x = 31, y = 31*3*1 = 93 < 100 
    max(2,3): x = 39, y = 39*3*9 = 1053 > 200 
    // partially in range, check longer prefix 
    // others outside of range, omitted for brevity 
    sp(32) = 192 // in range - increment count 
    min(2,4): x = 41, y = 41*4*1 = 164 < 200 
    max(2,4): x = 49, y = 49*4*9 = 1764 > 200 
    // partially in range, check longer prefix 
    // others outside of range, omitted for brevity 
    sp(41) = 164 // in range - increment count 
    min(2,5): x = 51, y = 51*5*1 = 255 > 200 
    // not in range, nothing to do 
    // no need to process (2,6..9), since these are all > min(2,5) > 200 

// check 3 digits 
min(3,): x = 111, y = 111*1*1*1 = 111 < 200 
max(3,): x = 999, y = 999*9*9*9 = 728271 > 200 
    // partially in range, check longer prefix 
    min(3,1): x = 111, y = 111*1*1*1 = 111 < 200 
    max(3,1): x = 199, y = 199*1*9*9 = 16119 > 200 
    // partially in range, check longer prefix 
    min(3,11): x = 111, y = 111*1*1*1 = 111 < 200 
    max(3,11): x = 119, y = 119*1*1*9 = 1071 > 200 
     // partially in range, check longer prefix 
     // others outside of range, omitted for brevity 
     sp(111) = 111 // in range - increment count 
    min(3,12): x = 121, y = 121*1*2*1 = 242 > 200 
     // not in range, nothing to do 
    // no need to process (3,13..19), since these are all > min(3,12) > 200 
    min(3,2): x = 211, y = 211*2*1*1 = 411 > 200 
    // not in range, nothing to do 
    // no need to process (3,3..9), since these are all > min(3,2) > 200 

// check 4 digits 
min(4,): x = 1111, y = 1111*1*1*1 = 1111 > 200 
    // not in range, nothing to do 
// no need to check more digits, since min(n,) > min(n-1,) and min(4,) > 200 

所以總數是8自營產品導致範圍爲100〜200

注意，有時我檢查範圍的開始，有時結束。這只是爲了表明在特定情況下哪些條件很重要。

只是爲了說明的東西，如果範圍是一直1-200，具有前綴1爲2個數字號碼的範圍是[11171]如上述，和1 < = 11 < = 171 < = 200，因此我們可以只包含所有2位數的前綴1，其中有9位。

實現：

我寫了一個小Java程序的基本實現。對於6萬到1億的數據，只需要不到一秒的時間，對於更多的數字（甚至是在這個範圍內），由於實現，會有算術溢出，所以所花費的時間是不可信的（除了我希望它應該只需要更長的時間（對於這個範圍），而不是更短）。

final static long[] tenPowers = {1, 10, 100, 1000, 10000, 100000, 1000000, 
    10000000, 100000000, 1000000000, 10000000000l, 100000000000l, 
    1000000000000l, 10000000000000l, 100000000000000l, 1000000000000000l, 
    10000000000000000l, 100000000000000000l, 1000000000000000000l}; 

public static void main(String args[]) throws InterruptedException 
{ 
    System.out.println("Count = "+selfProductCountRange(60000, 100000000000l)); 
} 

static long selfProductCountRange(long s, long f) 
{ 
    start = s; 
    finish = f; 
    long count = 0; 
    for (len = 1; ; len++) 
    { 
    long temp = selfProductCount(0, 0); 
    if (temp == -1) 
     break; 
    count += temp; 
    } 
    return count; 
} 

static long selfProduct(long num) 
{ 
    // pretend 0s are 1s for simplicity in the rest of the code 
    long selfProduct = num; 
    while (num > 0) 
    { 
    selfProduct *= Math.max(num % 10, 1); 
    num /= 10; 
    } 
    return selfProduct; 
} 

static long start, finish; 
static int len; 

static long selfProductCount(long prefix, int prefixLen) 
{ 
    long max = selfProduct((prefix+1) * tenPowers[len - prefixLen] - 1); 
    // overflow hack 
    if (max < 0) 
    max = finish+1; 
    if (max < start) 
    return 0; 
    long min; 
    if (prefixLen != 0) 
    min = selfProduct(prefix * tenPowers[len - prefixLen]); 
    else 
    min = selfProduct(tenPowers[len-1]); 
    if (min > finish) 
    return -1; 
    if (max <= finish && min >= start) 
    return getPossibilities(prefixLen); 
    long val = 0; 
    for (int i = 1; i < 10; i++) 
    { 
    long temp = selfProductCount(prefix*10+i, prefixLen+1); 
    if (temp == -1) 
     break; 
    val += temp; 
    } 
    return val; 
} 

static long getPossibilities(int prefixLen) 
{ 
    return (long)Math.pow(9, len-prefixLen); 
}