Cod sursa(job #316600)

Utilizator mottyMatei-Dan Epure motty Data 20 mai 2009 12:09:49
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<cstdio>
#include<queue>
#define N 2000001
using namespace std;
int a,b;

struct grf{
	int pred,val;
};

grf v[N];

queue <int> q;

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

int main()
{
	int x;
	freopen("multiplu.in","r",stdin);
	freopen("multiplu.out","w",stdout);
	scanf("%d",&a,&b);
	a=a*b / cmmdc(a,b);
	v[1].val=1;
	v[1].pred=0;
	q.push(1);
	while( q.back() )
	{
		x=(q.front()*10)%a;
		v[x].val=0;
		v[x].pred=q.front();
		q.push(x);
		x=(q.front()*10+1)%a;
		v[x].val=1;
		v[x].pred=q.front();
		q.push(x);
		q.pop();
	}
	x=0;
	while ( v[x].pred!=0 )
	{
		printf("%d",v[x].val);
		x=v[x].pred;
	}
	printf("1\n");
	return 0;
}