解説

整数 $x$ の十進表記における桁和を $\operatorname{ds}(x)$ とします。

求める値を

$$S= \sum_{\substack{1\le x\le N\\ \operatorname{ds}(x)\text{ が素数}}} x^K$$

とすると、この問題では $S\bmod PQ$ を求めます。

$P,Q$ は $P<Q$ を満たす異なる素数なので、

$$\gcd(P,Q)=1$$

です。

そこで、まず

$$S_P=S\bmod P$$

と

$$S_Q=S\bmod Q$$

をそれぞれ桁 DP で求めます。

最後に、中国剰余定理を用いて $S\bmod PQ$ を復元します。

以下では、法を $R$ として、

$$R=P$$

または

$$R=Q$$

の場合の答えを求める方法を説明します。同じ処理を $P,Q$ についてそれぞれ行います。

---

1. 補助変数を導入する

整数 $x$ の桁和を

$$s=\operatorname{ds}(x)$$

とします。

十進整数とその桁和は法 $9$ で合同なので、

$$x\equiv s\pmod 9$$

が成り立ちます。

したがって、

$$u=\frac{x-s}{9}$$

は整数です。

ここで、現在の整数 $x$ の末尾に数字 $d$ を追加したとします。

新しい整数 $x'$ と桁和 $s'$ は、

$$x'=10x+d,\qquad s'=s+d$$

です。

このとき、新しい補助変数 $u'$ は、

$$\begin{aligned} u' &=\frac{x'-s'}9\\ &=\frac{10x+d-(s+d)}9\\ &=\frac{10x-s}9\\ &=10\frac{x-s}9+s\\ &=10u+s \end{aligned}$$

となります。

よって、

$$\boxed{u'=10u+s}$$

です。

この式に、追加する数字 $d$ が含まれていないことが重要です。

なお、ここでの $(x-s)/9$ は整数上の割り算です。法 $R$ における $9$ の逆元を使っているわけではありません。

---

2. 桁 DP の状態

$N$ の桁数を $L$ とします。

$L$ 桁未満の整数についても、先頭に $0$ を補って $L$ 桁の整数として扱います。先頭に $0$ を補っても桁和は変化しません。

$N$ の先頭から何桁かを処理した時点で、

$$dp_j[s]$$

を次のように定義します。

• 現在の接頭辞が、$N$ の同じ長さの接頭辞より小さい
• 現在の桁和が $s$
• 補助変数が $u=(x-s)/9$

である接頭辞についての $u^j$ の総和を表すものとします。

すなわち、

$$dp_j[s] = \sum u^j \pmod R$$

です。

必要なのは、

$$0\le j\le K$$

の範囲だけです。

特に $j=0$ のときは、各接頭辞が $1$ を寄与するものと考えます。そのため、

$$dp_0[s]$$

は、条件を満たす接頭辞の個数です。

一方、まだ $N$ と完全に一致している接頭辞は常に $1$ 個しかありません。

そこで、一致している接頭辞については、

• equal_sum: 現在の桁和
• equal_u: 現在の $u\bmod R$

の $2$ つだけを別に管理します。

---

3. すでに $N$ より小さい状態からの遷移

現在の桁和が $s$ である接頭辞を考えます。

次の桁を追加した後の補助変数は、

$$u'=10u+s$$

です。

したがって、その $m$ 乗は二項定理より、

$$\begin{aligned} (u')^m &=(10u+s)^m\\ &=\sum_{j=0}^m \binom mj (10u)^j s^{m-j}\\ &=\sum_{j=0}^m \binom mj 10^j s^{m-j} u^j \end{aligned}$$

となります。

古い桁和が $s$ であるすべての接頭辞について、遷移後の $(u')^m$ を合計した値を $A_m[s]$ とすると、

$$\boxed{ A_m[s] = \sum_{j=0}^m \binom mj 10^j s^{m-j} dp_j[s] }$$

です。

この値は、次に追加する数字には依存しません。

次に追加する数字 $d$ は、

$$d=0,1,\ldots,9$$

のどれでも選べます。

古い桁和が $s$ なら、新しい桁和は $s+d$ です。

したがって、新しい桁和が $t$ である状態について、

$$\begin{aligned} ndp_m[t] &= \sum_{\substack{0\le d\le 9\\s+d=t}} A_m[s]\\ &= \sum_{s=t-9}^{t}A_m[s] \end{aligned}$$

となります。ただし、存在しない桁和は無視します。

よって、

$$\boxed{ ndp_m[t] = A_m[t]+A_m[t-1]+\cdots+A_m[t-9] }$$

です。

これは長さ $10$ の区間和です。

$t$ を $1$ 増やすとき、

• 新しく $A_m[t]$ を加える
• 範囲外になる $A_m[t-10]$ を引く

ことで更新できるため、スライド窓を用いて各 $m$ について線形時間で計算できます。

---

4. $N$ と一致している状態からの遷移

次に処理する $N$ の数字を $a$ とします。

現在まで $N$ と一致している接頭辞の桁和を $s_{\mathrm{eq}}$、補助変数を $u_{\mathrm{eq}}$ とします。

次の桁を追加した後の補助変数は、

$$u_{\mathrm{next}} = 10u_{\mathrm{eq}}+s_{\mathrm{eq}}$$

です。

次の数字として $d$ を選ぶとき、

• $d<a$ なら、この桁で初めて $N$ より小さくなる
• $d=a$ なら、引き続き $N$ と一致する
• $d>a$ なら、$N$ より大きくなるため選べない

となります。

$d<a$ を選んだ場合、新しい桁和は、

$$s_{\mathrm{eq}}+d$$

です。

また、$u_{\mathrm{next}}$ は $d$ に依存しません。

したがって、各

$$d=0,1,\ldots,a-1$$

について、

$$ndp_m[s_{\mathrm{eq}}+d] \mathrel{+}= u_{\mathrm{next}}^m$$

とします。

その後、$d=a$ を選んだ一致状態を、

$$u_{\mathrm{eq}}\gets u_{\mathrm{next}}$$ $$s_{\mathrm{eq}}\gets s_{\mathrm{eq}}+a$$

として次の桁へ引き継ぎます。

---

5. $x^K$ を復元する

補助変数の定義より、

$$x=9u+s$$

です。

したがって、二項定理から、

$$\begin{aligned} x^K &=(9u+s)^K\\ &= \sum_{j=0}^K \binom Kj (9u)^j s^{K-j}\\ &= \sum_{j=0}^K \binom Kj 9^j s^{K-j} u^j \end{aligned}$$

となります。

よって、桁和が $s$ である $x<N$ 全体についての $K$ 乗和は、

$$\boxed{ \sum_{j=0}^K \binom Kj 9^j s^{K-j} dp_j[s] }$$

です。

これを、素数である桁和 $s$ について合計します。

---

6. $N$ 自身を加える

DP に格納されているのは、

$$0\le x<N$$

を満たす整数です。

そのため、最後に $N$ 自身の桁和が素数なら、

$$N^K\bmod R$$

を答えに加えます。

一致状態として管理していた equal_u と equal_sum を使うと、

$$N=9u+\operatorname{ds}(N)$$

なので、

$$N\equiv 9\cdot \texttt{equal\_u} +\texttt{equal\_sum} \pmod R$$

として $N\bmod R$ を復元できます。

なお、DP には $x=0$ も含まれます。しかし、$0$ の桁和は $0$ であり素数ではないため、答えには影響しません。

以上の桁 DP により、法 $R$ における答えを求められます。

この処理を $R=P$ と $R=Q$ についてそれぞれ行い、

$$S_P=S\bmod P$$

および

$$S_Q=S\bmod Q$$

を求めます。

---

7. 中国剰余定理による復元

次の連立合同式を満たす $S_0$ を求めます。

$$S_0\equiv S_P\pmod P$$ $$S_0\equiv S_Q\pmod Q$$

まず、

$$S_0=S_P+Pt$$

と置きます。

この式は必ず、

$$S_0\equiv S_P\pmod P$$

を満たします。

もう一方の条件から、

$$S_P+Pt\equiv S_Q\pmod Q$$

すなわち、

$$Pt\equiv S_Q-S_P\pmod Q$$

です。

$P,Q$ は異なる素数なので、$P$ は法 $Q$ で逆元を持ちます。

したがって、

$$t\equiv (S_Q-S_P)P^{-1} \pmod Q$$

です。

$0\le t<Q$ を満たす代表元を選べば、

$$\boxed{ S_0 = S_P + P\left( (S_Q-S_P)P^{-1}\bmod Q \right) }$$

となります。

$Q$ は素数なので、フェルマーの小定理から、

$$P^{-1}\equiv P^{Q-2}\pmod Q$$

です。

また、

$$0\le S_P<P,\qquad 0\le t<Q$$

なので、

$$0\le S_0<PQ$$

です。

したがって、この $S_0$ がそのまま $S\bmod PQ$ の答えになります。

---

正当性の証明

補題 1

整数 $x$ の桁和を $s$、補助変数を

$$u=\frac{x-s}{9}$$

とする。

$x$ の末尾に数字 $d$ を追加した後の補助変数は、

$$u'=10u+s$$

である。

証明

新しい整数と桁和は、

$$x'=10x+d,\qquad s'=s+d$$

なので、

$$\begin{aligned} u' &=\frac{x'-s'}9\\ &=\frac{10x+d-(s+d)}9\\ &=\frac{10x-s}9\\ &=10\frac{x-s}9+s\\ &=10u+s \end{aligned}$$

です。

よって成立します。$\square$

---

補題 2

すでに $N$ より小さい接頭辞からの遷移後、$ndp_m[t]$ は、新しい桁和が $t$ である接頭辞についての $(u')^m$ の総和になる。

証明

古い桁和が $s$ である状態では、補題 1 より、

$$u'=10u+s$$

です。

二項定理から、

$$(u')^m = \sum_{j=0}^m \binom mj 10^j s^{m-j} u^j$$

なので、古い桁和が $s$ であるすべての状態について合計すると、

$$A_m[s] = \sum_{j=0}^m \binom mj 10^j s^{m-j} dp_j[s]$$

が得られます。

次の数字 $d$ は $0$ から $9$ まで自由に選べ、新しい桁和は $s+d$ です。

したがって、新しい桁和が $t$ になるすべての遷移の総和は、

$$\sum_{s=t-9}^{t}A_m[s]$$

です。

これは $ndp_m[t]$ の計算と一致します。$\square$

---

補題 3

各桁の処理後、DP は $N$ の同じ長さの接頭辞より小さい接頭辞を、重複も不足もなく表している。

証明

処理した桁数についての帰納法で示します。

$0$ 桁を処理した時点では、$N$ より小さい接頭辞は存在せず、空の接頭辞が $N$ と一致している状態だけが存在します。

ある桁数まで主張が成立していると仮定します。

すでに $N$ より小さい接頭辞については、次の数字として $0,1,\ldots,9$ のすべてを選べます。これらは補題 2 の遷移によってすべて DP に追加されます。

一方、$N$ と一致している接頭辞について、次の $N$ の数字を $a$ とすると、

• $d<a$ を選んだものは、新たに $N$ より小さくなる
• $d=a$ を選んだものは、引き続き $N$ と一致する
• $d>a$ を選んだものは、$N$ を超えるため除外される

となります。

各接頭辞がどの遷移から生成されるかは一意なので、重複も不足もありません。

よって、次の桁を処理した後についても主張が成立します。$\square$

---

補題 4

calc_mod は、求める総和を法 $R$ で正しく計算する。

証明

補題 3 より、すべての桁を処理した後の DP は、

$$0\le x<N$$

を満たすすべての整数を正しく表しています。

各整数について、

$$x=9u+s$$

であるため、

$$x^K = \sum_{j=0}^K \binom Kj 9^j s^{K-j} u^j$$

と展開できます。

DP は各 $u^j$ の総和を保持しているので、この式から、桁和が $s$ である整数の $K$ 乗和を正しく復元できます。

素数である桁和 $s$ だけを合計するため、条件を満たす $x<N$ のみが答えに加算されます。

さらに、$N$ 自身の桁和が素数である場合に限り $N^K$ を加えるため、条件を満たすすべての $1\le x\le N$ がちょうど一度ずつ数えられます。

よって、calc_mod は求める総和を法 $R$ で正しく計算します。$\square$

---

補題 5

中国剰余定理によって復元した値 $S_0$ は、求める総和と法 $PQ$ で合同である。

証明

構成から、

$$S_0\equiv S_P\equiv S\pmod P$$

および、

$$S_0\equiv S_Q\equiv S\pmod Q$$

です。

$P,Q$ は互いに素なので、中国剰余定理より、この連立合同式の解は法 $PQ$ で一意です。

したがって、

$$S_0\equiv S\pmod{PQ}$$

です。$\square$

---

定理

このアルゴリズムは、桁和が素数である $N$ 以下の正整数の $K$ 乗和を、法 $PQ$ で正しく求める。

証明

補題 4 より、桁 DP によって $S_P$ と $S_Q$ を正しく求められます。

さらに補題 5 より、それらを中国剰余定理で復元した値は、求める総和と法 $PQ$ で合同です。

よって、アルゴリズムは正しいです。$\square$

---

計算量

$L=|N|$ とします。

$i$ 桁を処理した時点で、桁和は高々 $9i$ です。そのため、各桁で扱う桁和状態数は $O(L)$ です。

各桁和 $s$ について、すべての $m,j$ の組を処理する回数は、

$$\sum_{m=0}^K(m+1)=O(K^2)$$

です。

したがって、法を $1$ つ固定したときの時間計算量は、

$$O(K^2L^2)$$

です。

これを $P,Q$ の $2$ 回行いますが、定数倍が増えるだけなので、全体の時間計算量も、

$$\boxed{O(K^2L^2)}$$

です。

中国剰余定理で必要な逆元の計算には $O(\log Q)$ 時間かかります。

遷移係数を事前計算するため、メモリ使用量は、

$$\boxed{O(K^2L)}$$

です。

$P$ と $Q$ に対する桁 DP は順番に実行するため、両方の DP 配列を同時に保持する必要はありません。

制約では、

$$L\le 300,\qquad K\le 10$$

です。

---

想定解コード（Python）