ネーミング：
sp(x) = Self-Product(x) = y
Range = a to b
ノート：
カウントが必要なだけだと思いますが、これを拡張して実際にすべての数値を出力することは難しくありません。
基本的な考え方 -xを特定の数のプレフィックスと特定の桁数を持つように分割し、一部の桁数 + プレフィックスが範囲内にあるかどうかを完全に (可能性の数を追加し、計算しやすく)、部分的に (より長いプレフィックスをチェックする) またはまったくしない (移動する)。
then = 0xであるため、0 を含む数値は許可されないことに注意してください。y
このアルゴリズムにはいくつかの非効率性があるかもしれませんが、適切な出発点を提供するはずです。改善点の 1 つは、バイナリ検索のようなプロセスを実行できるようにすることです。ここにはある程度の冗長性があるため、最小/最大を常に再計算するわけではありません。
表記法:
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))を含む最小値のセット - c 桁と d から e までの
max(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 の場合は 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);
}