Cod sursa(job #204368)

Utilizator devilkindSavin Tiberiu devilkind Data 23 august 2008 10:51:32
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <stdio.h>

#define NMAX 2000010

int A,B,X;
int cd[NMAX][3];
char R[NMAX];
int k,i,poz,x;
char v[NMAX];

int gcd(int x, int y)
{
	int r;
	

	do
	{
		r=x%y;
		x=y;
		y=r;
	}
	while (r);
	
	return x;
}

int main()
{
	freopen("multiplu.in","r",stdin);
	freopen("multiplu.out","w",stdout);

	scanf("%d %d",&A,&B);
	
	X=A*B/gcd(A,B);

	cd[1][0]=1;cd[1][1]=0;cd[1][2]=1;
	k=1;

	for (i=1;i<=k;i++)
	{
	//	printf("%d %d %d\n",cd[i][0],cd[i][1],cd[i][2]);
		if (cd[i][0]==0) {poz=i;break;}

		x=(cd[i][0]*10)%X;
		if (!R[x]) {cd[++k][0]=x;cd[k][1]=i;cd[k][2]=0;R[x]=1;}

		x=(x+1)%X;
		if (!R[x]) {cd[++k][0]=x;cd[k][1]=i;cd[k][2]=1;R[x]=1;}
	}

	int L=0;
	
	for (i=poz;i;i=cd[i][1]) L++;

	for (i=poz,k=L;i;i=cd[i][1],k--) 
		v[k]=cd[i][2];
	
	for (i=1;i<=L;i++) printf("%d",v[i]);
	return 0;
}