Submission #1781165

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>

#define loop(i, num)  for (int i = 0; i < num; i++)

using namespace std;

int n;

vector<int> dist;

deque<int> todo;

int main() {
    
    cin >> n;
    
    dist.resize(n);
    
    loop (i, n) {
        
        dist[i] = 1e9 + 7;
        
    }
    
    dist[1] = 1;
    
    todo.push_back(1);
    
    while (todo.size()) {
        
        int tmp = todo.front();
        
        todo.pop_front();
        
        if (dist[(10 * tmp) % n] > dist[tmp]) {
            
            dist[(10 * tmp) % n] = dist[tmp];
            
            todo.push_front((10 * tmp) % n);
            
        }
        
        if (dist[(tmp + 1) % n] > dist[tmp] + 1) {
            
            dist[(tmp + 1) % n] = dist[tmp] + 1;
            
            todo.push_back((tmp + 1) % n);
            
        }
        
    }
    
    cout << dist[0] << endl;
    
    return 0;
    
}

Submission Info

Judge Result