Cod sursa(job #199353)

Utilizator wefgefAndrei Grigorean wefgef Data 18 iulie 2008 02:09:04
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <cstdio>
#include <cstring>

#define MAX_N 2000005
#define INF 0x3f3f3f3f

int n;
int a, b;
int best[MAX_N];
int par[MAX_N];
char cif[MAX_N];
char num[MAX_N];
int q[MAX_N], qb, qe;

inline int gcd(int a, int b) {
	return !b ? a : gcd(b, a%b);
}

int main() {
	freopen("multiplu.in", "r", stdin);
	freopen("multiplu.out", "w", stdout);

	scanf("%d %d", &a, &b);
	n = a * b / gcd(a, b);

	memset(best, INF, sizeof(best));

	best[1 % n] = 1;
	cif[1 % n] = 1;

	q[qb = qe = 1] = 1 % n;
	while (best[0] == INF) {
		int val = q[qb++];

		if (best[val] + 1 < best[(val * 10) % n]) {
			par[(val * 10) % n] = val;
			cif[(val * 10) % n] = 0;
			best[(val * 10) % n] = best[val] + 1;
			q[++qe] = (val * 10) % n;
		}

		if (best[val] + 1 < best[(val * 10 + 1) % n]) {
			par[(val * 10 + 1) % n] = val;
			cif[(val * 10 + 1) % n] = 1;
			best[(val * 10 + 1) % n ] = best[val] + 1;
			q[++qe] = (val * 10 + 1) % n;
		}
	}

	int r = 0;
	for (int i = best[0]; i; --i) {
		num[i] = cif[r];
		r = par[r];
	}

	for (int i = 1; i <= best[0]; ++i)
		printf("%d", num[i]);
}