提出 #31964384

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, f[N], in[N];
int main() {
#ifdef ALEX_WEI
  freopen("1.in", "r", stdin);
  freopen("1.out", "w", stdout);
#endif
  cin >> n;
  memset(f, 0x3f, sizeof(f));
  queue<int> q;
  q.push(1), f[1] = 1;
  while(!q.empty()) {
    int t = q.front();
    q.pop(), in[t] = 0;
    int it = t * 10 % n;
    if(f[t] < f[it]) {
      f[it] = f[t];
      if(!in[it]) q.push(it);
    }
    it = (t + 1) % n;
    if(f[t] + 1 < f[it]) {
      f[it] = f[t] + 1;
      if(!in[it]) q.push(it);
    }
  }
  cout << f[0] << endl;
  return cerr << "Time: " << clock() << endl, 0;
}
/*
2022/5/26
start coding at 20:06
finish debugging at 20:08
*/

提出情報

ジャッジ結果