Cod sursa(job #593098)

Utilizator darrenRares Buhai darren Data 1 iunie 2011 11:58:22
Problema Multiplu Scor 100
Compilator cpp Status done
Runda pregatire_lot_juniori_1 Marime 0.81 kb
#include<fstream>
#include<vector>
using namespace std;

ofstream fout("multiplu.out");

inline int cmmdc(int a, int b)
{
	if (b == 0)
		return a;
	return cmmdc(b, a % b);
}
void rec(int i);

int q[2000000], p1 = 1, p2 = 1, a, b;
vector<bool> v(2000000);
int c[2000000], t[2000000];

int m;
int main()
{
	ifstream fin("multiplu.in");
	fin >> a >> b;
	
	q[p2] = 1;
	c[p2] = 1;
	v[1] = true;
	m = a * b / cmmdc(a, b);
	
	while (p1 <= p2)
	{
		int now = q[p1];
		
		for (int i = 0; i <= 1; ++i)
		{
			int aux = (now * 10 + i) % m;
			if (!v[aux])
			{
				v[aux] = true;
				q[++p2] = aux;
				t[p2] = p1, c[p2] = i;
			}
			if (aux == 0)
			{
				rec(p2);
				return 0;
			}
		}
		++p1;
	}
	return 0;
}

void rec(int i)
{
	if (i == 0)
		return;
	rec(t[i]);
	fout << c[i];
}