Cod sursa(job #393601)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 9 februarie 2010 18:34:43
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<cstdio>
#define N (1<<21) 
int q[N],M,a,b,R[N],up[N];
bool viz[N],digit[N];
int gcd(int a, int b)
{ return b ? gcd(b, a%b) : a; }

int bf()
{
	int p=0,u=0;
		
	q[u]=1;
	viz[1]=1;
	digit[0] = 1;
	while(p<=u)
	{
		int nr=q[p];
		int cnr=(nr*10)%M;
		if (!viz[cnr])
		{	q[++u]=cnr;viz[cnr]=1;digit[u]=0;up[u]=p; }
		if(!cnr)return u;
		cnr=(nr*10+1)%M;
		if (!viz[cnr])
		{	q[++u]=cnr;viz[cnr]=1;digit[u]=1;up[u]=p; }
		if (!cnr)return u;
		p++;
	}
	return -1;
}
int main()
{
	freopen("multiplu.in","r",stdin);
	freopen("multiplu.out","w",stdout);
	
	scanf("%d%d",&a,&b);
	
	M=a*(b/gcd(a,b));
	int p=bf(), nr=0;
	
	up[0] = -1;
	for (; p >= 0; p = up[p])
		R[++nr] = digit[p];
	for (; nr; nr--)
		printf("%d", R[nr]);
	printf("\n");
	
	return 0;
}