Cod sursa(job #890989)

Utilizator ELHoriaHoria Cretescu ELHoria Data 25 februarie 2013 13:03:30
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>

using namespace std; 

ifstream cin("multiplu.in");
ofstream cout("multiplu.out");

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

const int MMAX = int(2e6);
int A, B;
int M;
int Q[MMAX], T[MMAX];
bool use[MMAX], digit[MMAX];

void build(int i) {
	if(i == 0) {
		cout<<1;
		return;
	}
	build(T[i]);
	cout<<digit[i];
}

int main()
{
	cin>>A>>B;
	M = A*B/gcd(A,B);
	int L, R;
	R = L = 0;
	Q[R++] = 1;
	digit[0] = 1;
	for(;!use[0] && L < R;L++) {
		int r = Q[L]*10%M;
		if(use[r] == false) {
			use[r] = true;
			digit[R] = 0;
			T[R] = L;
			Q[R++] = r;
		}
		r = (Q[L]*10 + 1)%M;
		if(use[r] == false) {
			use[r] = true;
			digit[R] = 1;
			T[R] = L;
			Q[R++] = r;
		}
	}
	if(Q[R - 1] == 0) {
		build(R - 1);
	} else {
		build(R - 2);
	}
	return 0;
}