Cod sursa(job #129364)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 29 ianuarie 2008 10:00:33
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <stdio.h>
#include <math.h>

#define n 2000000

long a, b, m, r[n], ul[n], p, u, i;
char viz[n], cif[n];

long gcd(long a, long b) {
	if (!b) {
		return a;
	} else {
		return gcd(b, a % b);
	}
	return 1;
}

void rez(long i) {
	if (ul[i] == -1) {
		printf("%c", cif[i]);
		return;
	}
	rez(ul[i]);
	printf("%c", cif[i]);
}

int main() {
	freopen("multiplu.in", "r", stdin);
	freopen("multiplu.out", "w", stdout);
	scanf("%ld%ld", &a, &b);
	m = a / gcd(a, b) * b;
	if (m == 1) {
		printf("1");
		return 0;
	}
	r[0] = 1;
	cif[0] = '1';
	ul[0] = - 1;
	for (p = 0; true; ++p) {
		i = (r[p] * 10) % m;
		if (!viz[i]) {
			r[++u] = i;
			cif[u] = '0';
			viz[i] = 1;
			ul[u] = p;
			if (i == 0) {
				break;
			}
		}
		i = (i + 1) % m;
		if (!viz[i]) {
			r[++u] = i;
			cif[u] = '1';
			viz[i] = 1;
			ul[u] = p;
			if (i == 0) {
				break;
			}
		}
	}
	rez(u);
	return 0;
}