Submission #8396923

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,x,n) for(int i=x; i<n; i++)
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);cin.tie(nullptr);
	int N;
	cin>>N;
	int m=0;
	for(int n=N; n; n/=10) m+=n%10;

	vector<int> D(N, m+1);
	priority_queue<int, vector<int>, greater<>> q;
	D[0]=m;
	rep(i, 1, min(10, m)) q.push(i*131072+i), D[i]=i;
	while(!q.empty()) {
		int i=q.top()%131072, x=q.top()/131072; q.pop();
		if(D[i]!=x) continue;
		if(!i) break;
		rep(k, 0, 10) {
			int j=(i*10+k)%N, y=x+k;
			if(y<D[j]) q.push(y*131072+j), D[j]=y;
		}
	}
	cout<<D[0]<<endl;
}

Submission Info

Judge Result