E - 桁の積と倍数 / Product of Digits and Multiples 解説 by admin
gemini-3.5-flash-thinking概要
\(1\) 以上 \(N\) 以下の整数のうち、各桁の数字を掛け合わせた「桁積」が \(0\) でなく、かつ \(M\) の倍数であるものの個数を求める問題です。
\(N \le 10^{18}\) という非常に大きな値に対処するため、桁DP（桁動的計画法）を用いて高速に数え上げます。
考察
1. 桁積が \(0\) にならない条件
桁積が \(0\) にならないためには、数の中に 0 という数字が一度も登場してはいけないというルールに言い換えることができます。
ただし、例えば \(N = 123\) のときに \(12\) という数を考える場合、実質的に先頭に 0 が補われている（012 のように表される）とみなせます。この「数が始まる前のリーディングゼロ」は桁積の 0 としてカウントしてはいけません。
したがって、DPの状態として「すでに数字が始まっているか（started）」を持ち、数が始まって以降は 0 を選ばないように遷移を制限する必要があります。
2. \(M\) の倍数判定と素因数
使用できる数字は \(1\) から \(9\) のみです。これらの数字を構成する素因数は \(2, 3, 5, 7\) のみです。
このことから、以下の重要な性質が導かれます。
* \(M\) が \(2, 3, 5, 7\) 以外の素因数（例: \(11\) や \(13\) など）を持つ場合、どのように数字を掛け合わせても桁積が \(M\) の倍数になることはありません。この場合、答えは常に 0 となります。
* \(M\) を素因数分解して \(M = 2^a \times 3^b \times 5^c \times 7^d\) と表せるとき、桁積が \(M\) の倍数であるための必要十分条件は、桁積に含まれる素因数 \(2, 3, 5, 7\) の個数がそれぞれ \(a, b, c, d\) 以上であることです。
3. 状態数の削減
\(M \le 500\) という制約から、必要な各素因数の最大個数 \(a, b, c, d\) は非常に小さくなります。 * \(2^8 = 256 < 500 \implies a \le 8\) * \(3^5 = 243 < 500 \implies b \le 5\) * \(5^3 = 125 < 500 \implies c \le 3\) * \(7^3 = 343 < 500 \implies d \le 3\)
桁積の素因数の個数が \(a, b, c, d\) を超えた場合、それ以上個数が増えても「\(M\) の倍数である」という判定には影響しません。したがって、DPで保持する素因数の個数は、それぞれ \(a, b, c, d\) を上限として丸める（サチュレートさせる）ことで、状態数を劇的に削減できます。
アルゴリズム
桁DPの設計
以下のような多次元配列 dp を定義します。
dp[i][less][started][w][x][y][z]
* i : 上から何桁目まで決定したか (\(0 \le i \le L\), \(L\) は \(N\) の桁数で最大 \(18\))
* less : \(N\) 未満であることが確定しているか (\(0\): 未確定, \(1\): 確定)
* started : 数が既に始まっているか (\(0\): まだ始まっていない, \(1\): 始まっている)
* w, x, y, z : これまでの桁積に含まれる素因数 \(2, 3, 5, 7\) の個数（それぞれ \(a, b, c, d\) が上限）
遷移
各ステップ i において、次に置く数字 dig を決定します。
まだ数が始まっていない場合 (
started == 0)0を置く: 数はまだ始まりません。次の状態はstarted = 0のままで、素因数カウントもすべて0です。1から9を置く: 数が始まります。次の状態はstarted = 1になり、選んだ数字digが持つ素因数の数をカウントに加えます。
すでに数が始まっている場合 (
started == 1)1から9を置く:0は置けません。選んだ数字digが持つ素因数の数をこれまでのカウントに加算し、それぞれの上限（\(a, b, c, d\)）で丸めます。
※ dig の上限は、less が \(0\) なら \(N\) の \(i\) 桁目の数字、less が \(1\) なら \(9\) となります。
初期状態と答え
- 初期状態:
dp[0][0][0][0][0][0][0] = 1 - 求める答え:
dp[L][0][1][a][b][c][d] + dp[L][1][1][a][b][c][d]
（すべての桁を決め終え、数が始まっており、必要な素因数をすべて満たしているものの総和）
計算量
時間計算量
DPの各状態の遷移数は高々 \(10\) 通り（数字 \(0 \sim 9\) の選択）です。
状態数は最大でも以下のように見積もれます。
* 桁数 \(L \le 18\)
* less \(\in \{0, 1\}\) （\(2\) 通り）
* started \(\in \{0, 1\}\) （\(2\) 通り）
* \(w \le a \le 8\) （最大 \(9\) 通り）
* \(x \le b \le 5\) （最大 \(6\) 通り）
* \(y \le c \le 3\) （最大 \(4\) 通り）
* \(z \le d \le 3\) （最大 \(4\) 通り）
全体の遷移回数は、最大でも： $\(18 \times 2 \times 2 \times 9 \times 6 \times 4 \times 4 \times 9 \approx 5.9 \times 10^5 \text{ 回}\)\( となり、実行時間制限に対して余裕で間に合います。 - 時間計算量: \)O(L \cdot \log(M)^4)$ （実質的に数万〜数十万回程度のループ）
空間計算量
DPテーブルのサイズは、 20 * 2 * 2 * 10 * 7 * 5 * 5 要素の long long 型配列です。
- 空間計算量: \(O(L \cdot \log(M)^4)\) （メモリ消費量は数メガバイト程度で、非常に軽量です）
実装のポイント
素因数テーブルの用意: 各数字 \(0 \sim 9\) が持つ素因数 \(2, 3, 5, 7\) の個数を
factors[10][4]のような二次元配列で静的に持っておくと、遷移時の加算処理が非常にシンプルに書けます。\(M\) のプレチェック: 入力された \(M\) を \(2, 3, 5, 7\) で割っていき、最後に \(1\) にならなければ、その時点で \(0\) を出力して終了（早期リターン）させます。これにより、余計なDPテーブルのアクセスを防ぐことができます。
ソースコード
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
long long dp[20][2][2][10][7][5][5];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long N, M;
if (!(cin >> N >> M)) return 0;
int a = 0, b = 0, c = 0, d = 0;
long long temp = M;
while (temp % 2 == 0) { a++; temp /= 2; }
while (temp % 3 == 0) { b++; temp /= 3; }
while (temp % 5 == 0) { c++; temp /= 5; }
while (temp % 7 == 0) { d++; temp /= 7; }
if (temp > 1) {
cout << 0 << "\n";
return 0;
}
string S = to_string(N);
int L = S.length();
int factors[10][4] = {
{0, 0, 0, 0}, // 0
{0, 0, 0, 0}, // 1
{1, 0, 0, 0}, // 2
{0, 1, 0, 0}, // 3
{2, 0, 0, 0}, // 4
{0, 0, 1, 0}, // 5
{1, 1, 0, 0}, // 6
{0, 0, 0, 1}, // 7
{3, 0, 0, 0}, // 8
{0, 2, 0, 0} // 9
};
dp[0][0][0][0][0][0][0] = 1;
for (int i = 0; i < L; ++i) {
int num = S[i] - '0';
for (int less = 0; less < 2; ++less) {
for (int started = 0; started < 2; ++started) {
for (int w = 0; w <= a; ++w) {
for (int x = 0; x <= b; ++x) {
for (int y = 0; y <= c; ++y) {
for (int z = 0; z <= d; ++z) {
long long val = dp[i][less][started][w][x][y][z];
if (val == 0) continue;
if (started == 0) {
// 0 を置く（まだ始まらない）
dp[i+1][1][0][0][0][0][0] += val;
// 1 から 9 を置く
int limit = less ? 9 : num;
for (int dig = 1; dig <= limit; ++dig) {
int next_less = less || (dig < num);
int nw = min(a, factors[dig][0]);
int nx = min(b, factors[dig][1]);
int ny = min(c, factors[dig][2]);
int nz = min(d, factors[dig][3]);
dp[i+1][next_less][1][nw][nx][ny][nz] += val;
}
} else {
// すでに始まっている場合、0は置けない
int limit = less ? 9 : num;
for (int dig = 1; dig <= limit; ++dig) {
int next_less = less || (dig < num);
int nw = min(a, w + factors[dig][0]);
int nx = min(b, x + factors[dig][1]);
int ny = min(c, y + factors[dig][2]);
int nz = min(d, z + factors[dig][3]);
dp[i+1][next_less][1][nw][nx][ny][nz] += val;
}
}
}
}
}
}
}
}
}
long long ans = 0;
for (int less = 0; less < 2; ++less) {
ans += dp[L][less][1][a][b][c][d];
}
cout << ans << "\n";
return 0;
}
この解説は gemini-3.5-flash-thinking によって生成されました。
投稿日時:
最終更新: