Cod sursa(job #574955)

Utilizator SmarandaMaria Pandele Smaranda Data 7 aprilie 2011 18:48:22
Problema Multiplu Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<stdio.h>
long cmmdc (long a , long b)
{
	long r;
	while (r)
	{
		r=a%b;
		a=b;
		b=r;
	}
	return a;
}
struct MULTIPLU
{
	long c,r,pred;
};
MULTIPLU q[1000001];
long numar[1000001];
long viz[2000002];
int main()
{
	long a,b,p,u,i,gcd;
	
	freopen("multiplu.in","r",stdin);
	freopen("multiplu.out","w",stdout);
	
	scanf("%ld%ld",&a,&b);
	gcd=a*b/cmmdc(a,b);
	q[1].c=q[1].r=1;
	q[1].pred=0;
	p=u=1;
	while (1)
	{
		q[++u].c=1;
		q[u].pred=p;
		q[u].r=(q[p].r*10+1)%gcd;
		/*if (viz[q[p].r])
			u--;
		else
			viz[q[p].r]=1;*/
		if (q[u].r==0)
			break;
		q[++u].c=0;
		q[u].pred=p;
		q[u].r=(q[p].r*10)%gcd;
		/*if (viz[q[p].r])
			u--;
		else
			viz[q[p].r]=1;*/
		if (q[u].r==0)
			break;
		p++;
	}
	i=u;
	numar[++numar[0]]=q[i].c;
	i=q[i].pred;
	while (i)
	{
			numar[++numar[0]]=q[i].c;
			i=q[i].pred;
	}
	for (i=numar[0];i>=1;i--)
		printf("%ld",numar[i]);
	return 0;
}