Cod sursa(job #478751)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 20 august 2010 11:37:14
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <cstdio>
#include <queue>

using namespace std;

#define file_in "multiplu.in"
#define file_out "multiplu.out"

#define nmax 2000005 

int n,m,d;
queue<int> q;
char viz[nmax];
int st[nmax];

inline int cmmmc(int a, int b)
{
	int r,p;
	p=a*b;
	
	while(b)
	{
		r=a%b;
		a=b;
		b=r;
	}
	
	return p/a;
}

void citire()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &n, &m);
}

void recon(int i)
{
	if (i==1)
	{
		printf("1");
		return ;
	}
	recon(st[i]);
	if ((st[i]*10)%d==i)
        printf("0");
    else
		printf("1");
}

void solve()
{
	int s,x;
	d=cmmmc(n,m);
	q.push(1);
	viz[1]=1;
	for (;!q.empty();q.pop())
	{
		x=q.front();
		if (x==0)
		{
			recon(x);
			return ;
		}
		
		s=(x*10)%d;
		if (!viz[s])
		{
			viz[s]=1;
			st[s]=x;
			q.push(s);
		}
		s=(x*10+1)%d;
		if (!viz[s])
		{
			viz[s]=1;
			st[s]=x;
			q.push(s);
		}
	}
}

int main()
{
	citire();
	solve();
	
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}