Cod sursa(job #811107)

Utilizator dariusdariusMarian Darius dariusdarius Data 11 noiembrie 2012 15:30:11
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<stdio.h>
struct MyStruct{int t,r;bool c;};
MyStruct q[2000005];int sz;
bool viz[2000005],sol[2000005];
int cmmdc(int a,int b) {if(b==0) return a;  return cmmdc(b,a%b);}
int cmmmc(int a,int b) {return a*b/cmmdc(a,b);}
void reconst(int p)
{
	if(p==0) return;
	sol[++sz]=q[p].c;
	reconst(q[p].t);
}
void afis()
{
	int i;
	for(i=sz;i>=1;i--)
		printf("%d",(int)sol[i]);
	printf("\n");
}
int main()
{
	freopen("multiplu.in","r",stdin);
	freopen("multiplu.out","w",stdout);
	int a,b,p,u,r1;
	scanf("%d%d",&a,&b);
	const int MOD=cmmmc(a,b);
	p=1;u=0;
	q[++u].t=0;
	q[u].c=1;
	q[u].r=1;
	while(p<=u)
	{
		r1=(q[p].r*10+0)%MOD;
		if(viz[r1]==0)
		{
		q[++u].r=r1;
		q[u].t=p;q[u].c=0;
		viz[r1]=1;
		if(q[u].r==0) break;
		}
		
		r1=(q[p].r*10+1)%MOD;
		if(viz[r1]==0)
		{
		q[++u].r=(q[p].r*10+1)%MOD;
		q[u].t=p;q[u].c=1;
		viz[r1]=1;
		if(q[u].r==0) break;
		}
		p++;
	}
	reconst(u);
	afis();
	return 0;
}