Submission #2559040

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n; cin >> n;
  vector<int> dist(n, 9 * 5);
  dist[1] = 1;
  auto comp = [&](int a, int b) { return dist[a] < dist[b]; };
  priority_queue<int, vector<int>, decltype(comp)> pq(comp);
  pq.push(1);
  while(pq.size()) {
    int i = pq.top();
    pq.pop();
    if(dist[(i + 1) % n] > dist[i] + 1) {
      dist[(i + 1) % n] = dist[i] + 1;
      pq.push((i + 1) % n);
    }
    if(dist[i * 10 % n] > dist[i]) {
      dist[i * 10 % n] = dist[i];
      pq.push(i * 10 % n);
    }
  }
  cout << dist[0];
}

Submission Info

Judge Result