命名：
sp(x) = Self-Product(x) = y
Range = a to b
笔记：
我假设您只想要计数，但是将其扩展为实际打印所有数字应该不难。
基本思想 - 将x' 拆分为具有某些数字前缀和一定数量的数字，并确定某些数字 + 前缀是否在范围内，或者完全（添加可能性的数量，易于计算），部分（检查更长的前缀）或根本不检查（继续）。
请注意，x不允许任何包含 0 的数字，因为 then 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)）
通过示例算法：
我将使用 Range = 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 位数字的范围将是 [11,171] 如上所述，并且 1 <= 11 <= 171 <= 200，所以我们可以只包括前缀为 1 的所有 2 位数字，共有 9 个。
执行：
我写了一个带有基本实现的小 Java 程序。对于 60000 到 100000000000 来说，对于更大的数字（甚至在这个范围内），它需要不到一秒的时间，因为实现，会有算术溢出，所以所花费的时间不能真正被信任（除了，我希望它应该只需要更长的时间（对于这个范围），而不是更短）。
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);
}