Cod sursa(job #462644)

Utilizator mihai995mihai995 mihai995 Data 12 iunie 2010 15:21:55
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>
using namespace std;

int c[1<<21],a[1<<21];
bool cif[1<<21],used[1<<21];

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

void print(int x)
{
	if (!x)
		return;
	print(a[x]);
	out<<cif[x];
}

void work(int x)
{
	int i,p,u,w;
	p=u=1;
	c[1]=1;cif[1]=true;
	while (p<=u)
	{
		for (i=0;i<2;i++)
		{
			w=(c[p]*10+i)%x;
			if (!used[w])
			{
				used[w]=true;
				c[++u]=w;
				cif[u]=i;
				a[u]=p;
				if (!w)
				{
					print(u);
					return;
				}
			}
		}
		++p;
	}
}

int cmmdc(int a,int b)
{
	int c;
	while (b)
	{
		c=a%b;
		a=b;
		b=c;
	}
	return a;
}

int main()
{
	int a,b;
	in>>a>>b;
	work(a*b/cmmdc(a,b));
	return 0;
}