その桁の積が p になるような n 桁の数のカウントを取得するには、どのアルゴリズムを使用する必要がありますか? ここでの特別な条件は、どの桁も 1 であってはならないということです。
私がこれまで考えてきたのは、p の素因数分解を行うことです。n=3、p=24 とします。
最初に 24 を素因数分解して : 2*2*2*3 を取得します。
今、私はこれらの組み合わせを決定するのに問題があります
4*2*3 、 2*4*3 、 .... など たとえそうできたとしても... n が素数の数よりもはるかに小さい場合、どのようにスケーリングしますか。
それが正しい方向かどうかはわかりません...どんな意見でも歓迎します。
まず、完全な素数分解は実際には必要なく、底よりも小さい素数への分解のみが必要です (ここでは 10 を意味すると思いますが、問題は任意の底に一般化できます)。したがって、最初の 4 つの素数 (2、3、5、および 7) への因数分解のみが必要です。残りの (素数かどうかに関係なく) 因数が 1 より大きい場合、問題の解は 0 になります。
pここで、数値が次のように考慮されていると仮定します。
p = 2^d1 * 3^d2 * 5^d3 * 7^d4
nまた、次の数字から構成されます。
p =d (n-1) d (n-2) ...d 2 d 1 d 0
次に、桁を並べ替えると、次のようになります。
p = 2^q2 * 3^q3 * 4^q4 * 5^q3 * ... * 9^q9
どこqi >= 0とq2 + q3 + ... q9 = n
また、（因数分解による）：
for prime=2: d1 = q2 + 2*q4 + q6 + 3*q8
for prime=3: d2 = q3 + q6 + 2*q9
for prime=5: d3 = q5
for prime=7: d4 = q7
したがって、q5とq7は固定されており、方程式のすべての非負整数解を見つける必要があります:
(未知数は残りqiです: q2, q3, q4, q6, q8 and q9)
d1 = q2 + 2*q4 + q6 + 3*q8
d2 = q3 + q6 + 2*q9
n - d3 - d4 = q2 + q3 + q4 + q6 + q8 + q9
上記の解のそれぞれについて、次の式で見つけることができる桁の再配置がいくつかあります。
X = n! / ( q2! * q3! * ... q9! )
要約する必要があります。
これには、生成関数を使用した閉じた式がある可能性があります。Math.SE に投稿できます。
p=24、 の例n=3:
p = 2^3 * 3^1 * 5^0 * 7^0
そして、私たちは持っています:
d1=3, d2=1, d3=0, d4=0
次の整数解:
3 = q2 + 2*q4 + q6 + 3*q8
1 = q3 + q6 + 2*q9
3 = q2 + q3 + q4 + q6 + q8 + q9
は(q2, q3, q4, q6, q8, q9) =:
(2, 0, 0, 1, 0, 0)
(1, 1, 1, 0, 0, 0)
与える：
3! / ( 2! * 1! ) = 3
3! / ( 1! * 1! * 1! ) = 6
そして 3+6 = 9トータルソリューション。
p=3628800、 の例n=10:
p = 2^8 * 3^4 * 5^1 * 7^1
そして、私たちは持っています:
d1=8, d2=4, d3=1, d4=1
次の整数解:
8 = q2 + 2*q4 + q6 + 3*q8
4 = q3 + q6 + 2*q9
8 = q2 + q3 + q4 + q6 + q8 + q9
は(q2, q3, q4, q6, q8, q9)（対応する数字とソリューションごとの再配置とともに）：
(5, 0, 0, 0, 1, 2) 22222899 57 10! / (5! 2!) = 15120
(4, 0, 2, 0, 0, 2) 22224499 57 10! / (4! 2! 2!) = 37800
(4, 1, 0, 1, 1, 1) 22223689 57 10! / (4!) = 151200
(3, 2, 1, 0, 1, 1) 22233489 57 10! / (3! 2!) = 302400
(4, 0, 1, 2, 0, 1) 22224669 57 10! / (4! 2!) = 75600
(3, 1, 2, 1, 0, 1) 22234469 57 10! / (3! 2!) = 302400
(2, 2, 3, 0, 0, 1) 22334449 57 10! / (3! 2! 2!) = 151200
(2, 4, 0, 0, 2, 0) 22333388 57 10! / (4! 2! 2!) = 37800
(3, 2, 0, 2, 1, 0) 22233668 57 10! / (3! 2! 2!) = 151200
(2, 3, 1, 1, 1, 0) 22333468 57 10! / (3! 2!) = 302400
(1, 4, 2, 0, 1, 0) 23333448 57 10! / (4! 2!) = 75600
(4, 0, 0, 4, 0, 0) 22226666 57 10! / (4! 4!) = 6300
(3, 1, 1, 3, 0, 0) 22234666 57 10! / (3! 3!) = 100800
(2, 2, 2, 2, 0, 0) 22334466 57 10! / (2! 2! 2! 2!) = 226800
(1, 3, 3, 1, 0, 0) 23334446 57 10! / (3! 3!) = 100800
(0, 4, 4, 0, 0, 0) 33334444 57 10! / (4! 4!) = 6300
2043720私が間違いを犯していなければ、これは完全な解決策です..
次の式に基づいて、動的計画法のアプローチを使用できます。
f[ n ][ p ] = 9 * ( 10^(n-1) - 9^(n-1) ), if p = 0
0, if n = 1 and p >= 10
1, if n = 1 and p < 10
sum{ f[ n - 1 ][ p / k ] for 0 < k < 10, p mod k = 0 }, if n > 1
最初のケースは p = 0 の別のケースです。このケースは O(1) で計算され、4 番目のケースから k = 0 の値を除外するのに役立ちます。
2 番目と 3 番目のケースは動的ベースです。4 番目
のケースkは、最後の桁のすべての可能な値を順番に取り、同じ問題をより小さなサイズに縮小することによって、最後の桁kとの積pを使用して数の量を合計します。
暗記を使用して dp を実装すると、実行時間がO( n * p )になります。
PS：私の答えは、OPが説明したよりも一般的な問題に対するものです。どの桁も 1 に等しくないという条件を満たさなければならない場合、式は次のように調整できます。
f[ n ][ p ] = 8 * ( 9^(n-1) - 8^(n-1) ), if p = 0
0, if n = 1 and p >= 10 or p = 1
1, if n = 1 and 1 < p < 10
sum{ f[ n - 1 ][ p / k ] for 1 < k < 10, p mod k = 0 }, if n > 1
素数分解を計算するという、「難しい」問題として知られている問題に取り組むことから始めるとは思いません。とは、複雑さの厳密な計算ではなく、直感が意味しているとは思いません。
最終的には の 1 桁の約数だけに関心があるので、まずで割ってから で割ってpから で割っpて2、までいきます。もちろん、これらの除算の一部は整数の結果を生成しません。その場合、その数字は今後の考慮から除外できます。349
あなたの例では、 （つまり、除数と剰余のタプル）p = 24が得られます。{{2},12}, {{3},8}, {{4},6}, {{6},4}, {{8},3}今度はこのアプローチをもう一度適用しますが、今回は、数字が乗算されて剰余になる 2 桁の数字を探しています。つまり、{{2},12}が得られるから{{2,2},6},{{2,3},4},{{2,4},3},{{2,6},2}です。たまたま、これらの結果はすべて 3 桁の数字であり、その数字を掛けると24になりますが、一般に、残りの一部が 2 桁以上になる可能性があり、それらの点で検索ツリーをトリミングする必要があります。に戻って続行{{3},8}します。
このアプローチでは、すべてを列挙するため、考慮する必要がある一連の数字の順列の数を個別に計算する必要がなくなることに注意してください。また、含めるための個別の候補として2*2とを考慮する必要もありません。4
ちょっとしたメモ化でもこれをスピードアップできると思います。
組み合わせ論に詳しい人が、この問題の閉形式の解法を教えてくれることを楽しみにしています。
N桁の数字とその桁の積はpです。
たとえば、n=3およびp=24の場合
配置は次のようになります（順列）
= (p!)/(p-n)!
= (24!) /(24 -3)!
= (24 * 23 * 22 * 21 )! / 21 !
= (24 * 23 * 22 )
= 12144
だから12144のアレンジができます
組み合わせは以下の通りです
= (p!)/(n!) * (p-n)!
= (24!) /(3!) * (24 -3)!
= (24 * 23 * 22 * 21 )! / (3!) * 21 !
= (24 * 23 * 22 ) / 6
= 2024
これがあなたを助けますように
問題は不自然に見えますが、いずれにせよ、あなたが見たものには上限があります。たとえば、p は 1 桁である必要があるため (「その桁の積」)、7 を超える素数をもつことはできません。
したがって、p = 1 * 2^a * 3^b * 5^c * 7^d と仮定します。
2^a は、ceil(a/3) から 'a' 桁までの範囲で指定できます。3^b は ceil(b/2) から 'b' 桁まで可能です。5^c と 7^d は、それぞれ 'c' と 'd' の数字に由来します。残りの桁は 1 で埋めることができます。
したがって、n は ceil(a/3)+ceil(b/2)+c+d から無限大までの範囲であり、p は一連の固定値を持ちます。
素因数分解は正しい方向のように感じますが、7 より大きい素数は必要ないため、2、3、5、7 で繰り返し割ることができます。(素数が得られない場合、または素数が 7 より大きい場合、解はありません)。
素因数を取得したらp % x、p / x定数時間操作として実装できます (実際には は必要ありませんp。素因数を保持するだけでかまいません)。
私の考えは、以下のアルゴリズムで組み合わせを計算すると、そこからの順列は簡単です。
getCombinations(map<int, int> primeCounts, int numSoFar, string str)
if (numSoFar == n)
if (primeCounts == allZeroes)
addCombination(str);
else
;// do nothing, too many digits
else if (primeCounts[7] >= 1) // p % 7
getCombinations(primeCounts - [7]->1, numSoFar-1, str + "7")
else if (primeCounts[5] >= 1) // p % 5
getCombinations(primeCounts - [5]->1, numSoFar-1, str + "5")
else if (primeCounts[3] >= 2) // p % 9
getCombinations(primeCounts - [3]->2, numSoFar-1, str + "9")
getCombinations(primeCounts - [3]->2, numSoFar-2, str + "33")
else if (primeCounts[2] >= 3) // p % 8
getCombinations(primeCounts - [2]->3, numSoFar-1, str + "8")
getCombinations(primeCounts - [2]->3, numSoFar-2, str + "24")
getCombinations(primeCounts - [2]->3, numSoFar-3, str + "222")
else if (primeCounts[3] >= 1 && primeCounts[2] >= 1) // p % 6
getCombinations(primeCounts - {[2]->1,[3]->1}, numSoFar-1, str + "6")
getCombinations(primeCounts - {[2]->1,[3]->1}, numSoFar-2, str + "23")
else if (primeCounts[2] >= 2) // p % 4
getCombinations(primeCounts - [2]->2, numSoFar-1, str + "4")
getCombinations(primeCounts - [2]->2, numSoFar-2, str + "22")
else if (primeCounts[3] >= 1) // p % 3
getCombinations(primeCounts - [3]->1, numSoFar-1, str + "3")
else if (primeCounts[2] >= 1) // p % 2
getCombinations(primeCounts - [2]->1, numSoFar-1, str + "2")
else ;// do nothing, too few digits
物事が行われる順序を考えると、重複はないと思います。
改善：
は 7 で割り切れないことがわかっているため、 を一度確認p%7したら (スタックの奥深くまで) もう一度確認する必要はありません。p%5
primeCountsマップである必要はありません。長さ 4 の配列でもかまいません。また、コピーする必要もありません。値を適切に増減できます。同様のことがstr(文字配列) でも実行できます。
の桁数が多すぎる場合は、またはgetCombinations(..., str + "8")をチェックしても意味がありません。これと同様のチェックは、実装するのがそれほど難しくないはずです (関数が bool を返すようにするだけです)。"24""222"