D - Big mod Small

$N$ の上から $i$ 桁目を $N_i$ とし、$N$ から上 $i$ 桁を取り出した数を $U_i$ とします。
ここで、$N$ の $K$ 進数での桁数を $|N|$ としたとき、 $U_{|N|}=N$ です。

求めたい値は、$N\bmod M=U_{|N|}\bmod M$ です。

$$\begin{aligned} U_{i+1}&=KU_i+N_{i+1}\\ U_{i+1}\bmod M&=(KU_i+N_{i+1})\bmod M\\ U_{i+1}\bmod M&=(K(U_i\bmod M)+N_{i+1})\bmod M \end{aligned}$$

であることから、$U_i\bmod M$ のみを保持すればいいことが分かります。
上の漸化式を適切に実装することで $O(|N|)=O(\log N)$ で解くことができました。

実装例（C++）

1
2
3
4
5
6
7
8
9
10
11
12#include <bits/stdc++.h>
using namespace std;
int main()
{
  int K, M;
  string S;
  cin >> K >> M >> S;
  long long ans = 0;
  for (char c : S)
    ans = (ans * K + (c - '0')) % M;
  cout << ans << endl;
}