Untitled
#include "bits/stdc++.h" using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(x...) #endif using ll = long long; void test_case() { int k; cin >> k; unordered_set<int> s1; int g = 1; while (true) { if (s1.contains(g)) { break; } else { s1.insert(g); g = g * 10 % k; } } vector<int> s = {s1.begin(), s1.end()}; vector<int> d(k, 50); priority_queue<pair<int, int>> q; q.emplace(0, 0); while (!q.empty()) { auto [cost, rem] = q.top(); q.pop(); cost *= -1; if (cost > d[rem]) continue; for (int ost : s) { int v = (ost + rem) % k; if (d[v] > cost + 1) { d[v] = cost + 1; q.emplace(-d[v], v); if (v == 0) { break; } } } } cout << d[0]; } signed main() { ios::sync_with_stdio(false); cin.tie(NULL); int tests = 1; // cin >> tests; while (tests--) { test_case(); } return 0; }
Leave a Comment