# 2021-2022 ACM-ICPC Brazil Subregional Programming

## C. Creating Multiples

https://codeforces.com/gym/103388/problem/C

### 題幹

給定一個 $B$ 進位 $L$ 位數 ($2 \leq B \leq 10^4$, $1 \leq L \leq 2 \times 10^5$) 的數字 $N$ $(\{D_1, D_2, ..., D_L\})$ ，可以進行操作：將 $D_i$ 改為 $D'_i$ ($0 \leq D'_i < D_i$)。

對 $N$ 進行最多一次操作之後，找一個最小的數字 $N'$ $(\{D'_1, D'_2, ..., D'_L\})$ 滿足 $N' \equiv 0 \pmod{(B+1)}$。

### 題解

題目等價於找到修改的位置 $i$ 以及數字 $D_i$，滿足：

\begin{align}
(D_i - D'_i) \times B^{L-i} &\equiv N &\pmod{(B+1)}
\end{align}

枚舉 $i$ 以及 $D_i$ 的複雜度 $O(LB)$。TLE

將式子轉成：

\begin{align}
D_i \times B^{L-i} - D'_i \times B^{L-i} &\equiv N &\pmod{(B+1)} \\
D'_i \times B^{L-i} &\equiv D_i \times B^{L-i} - N &\pmod{(B+1)} \\
D'_i &\equiv (D_i \times B^{L-i} - N) \times (B^{L-i})^{-1} &\pmod{(B+1)}
\end{align}

其中 $(B^{L-i})^{-1}$ 為模逆元滿足 $(B^{L-i})^{-1} \times B^{L-i} \equiv 1 \pmod{(B+1)}$。

\begin{align}
&\gcd(B, B+1) = 1 \\
\Rightarrow &\gcd(B^k, B+1) = 1 \\
\Rightarrow &\exists (B^k)^{-1} \times B^k \equiv 1 \pmod{(B+1)}
\end{align}

故模逆元 $(B^{L-i})^{-1}$ 存在。

枚舉 $i$，擴展歐幾里得計算模逆元，複雜度 $O(L \lg B)$。

先建好 $1$ 到 $B$ 的模逆元的表後，枚舉 $i$ 查表，複雜度 $O(B+L)$。