Submission #2553829

---

Source Code Expand

#include <cstdio>
#include <queue>
using namespace std;

const int N = 1e5 + 10;
const int M = 2e6 + 10;
struct data {
	int val, cos;
	data(int _val = 0, int _cos = 0) {val = _val, cos = _cos;}
} q[M];
int K, vis[N];

template <class T> inline void in(T &x) {
	x = 0; int f = 1; char ch = getchar();
	for (; ch<'0' || ch>'9';) {if (ch=='-') f=-1; ch = getchar();}
	for (; ch>='0' && ch<='9';) x = x*10 + ch-'0', ch = getchar();
	x *= f;
}

inline int calc(int K) {
	int l = 0, r = 0; data u, v;
	for (q[++r] = data(1, 1); l < r;) {
		u = q[++l], vis[u.val] = 1;
		if (!u.val) return u.cos;
		v = data((u.val + 1) % K, u.cos + 1);
		if (!vis[v.val]) q[++r] = v;
		v = data((u.val * 10) % K, u.cos);
		if (!vis[v.val]) q[++r] = v;
	}
	return 0;
}

inline void work() {
	in(K), printf("%d\n", calc(K));
}

int main() {work(); return 0;}

Submission Info

Judge Result