Cod sursa(job #148475)

Utilizator sory1806Sandu Sorina-Gabriela sory1806 Data 4 martie 2008 13:15:26
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include<fstream.h>
#define nmax 2000000
int coada[nmax],pred[nmax];
char urm[nmax];
ifstream f("multiplu.in");
ofstream g("multiplu.out");

void write(int inc)
{
	if(pred[inc]>0)
		write(pred[inc]);
	g<<(int)urm[inc];
}

int cmmdc(int a, int b)
{       if(a==0)
		return b;
	if(b==0)
		return a;
	if(a>b)
		return cmmdc(a%b, b);
	else
		return cmmdc(a, b%a);
}

int main()
{    	int a, b, m, i, p, u, aux;
	f>>a>>b;
	m=(a*b)/cmmdc(a,b);
	coada[0]=1;
	pred[1]=-1;
	urm[1]=1;
	p=0; u=0;
	while(p<=u)
	{	for(i=0; i<2; i++)
		{	aux=(coada[p]*10+i)%m;
			if(!pred[aux])
			{	pred[aux]=coada[p];
				urm[aux]=i;
				coada[++u]=aux;
				if(pred[0])
				{    	write(0);
					g<<'\n';
					g.close();
					return 0;
				}
			}
		}
		p++;
    }
    return 0;
}