## Thuật toán
Xét một số $x$, giả sử ta thêm chữ số $c$ vào sau, thì $x$ trở thành $10 \times x + c$, suy ra
$$
f(10 \times x + c) \equiv f(x) + c \ \textrm{(mod } k\textrm{)}
$$
Khởi tạo các đỉnh của đồ thị là $0, 1, \ldots, k - 1$, tương ứng với các số dư khi chia cho $k$.
Với mỗi đỉnh $u$, ta chữ số $d \ (0 \leq d \leq 9)$ đằng sau số có $f(x) \equiv u \ \textrm{(mod } k\textrm{)}$, khi đó ta thêm vào đồ thị cung $(u, v)$ có trọng số $d$, với $v = (u\times 10 + d) \ \textrm{mod} \ k$.
Ta cần tìm $f(x)$ nhỏ nhất của số $x$ chia hết cho $k$, dễ thấy bài toán tương đương với tìm đường đi ngắn nhất đến đỉnh $0$.
$\rightarrow$ Đây là bài toán cơ bản của Dijkstra, ta có thể xử lí bằng cách đảo chiều các cung của đồ thị.
**Độ phức tạp.** $O((n + m) \log n)$
## Cài đặt tham khảo
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int MAXN = 1e5 + 5;
const int INF = 1e18 + 5;
int k;
vector<pii> adj[MAXN];
int dist[MAXN];
void init() {
cin >> k;
for (int u = 0; u < k; ++u) {
for (int w = 0; w <= 9; ++w) {
if (u == 0 && w == 0) continue;
int v = (u * 10 + w) % k;
adj[v].push_back({u, w});
}
}
}
void solve() {
fill(dist, dist + MAXN, INF);
dist[0] = 0;
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0, 0});
while (!pq.empty()) {
long long cost = pq.top().first;
long long u = pq.top().second;
pq.pop();
for (int i = 0; i < (int)adj[u].size(); ++i) {
long long v = adj[u][i].first;
long long w = adj[u][i].second;
if (dist[v] > cost + w) {
dist[v] = cost + w;
pq.push({dist[v], v});
}
}
}
int res = INF;
for (int i = 1; i <= 9; ++i) if (dist[i] != INF) res = min(res, dist[i] + i);
cout << res;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
init();
solve();
return 0;
}
```
chithanhnguyen
Created at
3 likes