Cod sursa(job #320688)

Utilizator mottyMatei-Dan Epure motty Data 5 iunie 2009 15:11:00
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<cstdio>
#include<queue>
#define N 2000001
using namespace std;
int a,b;

struct grf{
	int pred,val;
};

bool k[N];

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%d",&a,&b);
	a=a*b / cmmdc(a,b);
	k[1]=true;
	v[1].val=1;
	v[1].pred=0;
	q.push(1);
	while(!q.empty())
	{
		x=(q.front()*10)%a;
		if(k[x]==0)
		{
			v[x].val=0;
			v[x].pred=q.front();
			q.push(x);
			k[x]=1;
		}
		x=(q.front()*10+1)%a;
		if(k[x]==0)
		{
			k[x]=1;
			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;
}