Cod sursa(job #115834)

Utilizator vlad.maneaVlad Manea vlad.manea Data 17 decembrie 2007 00:15:52
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <stdio.h>
#define NMax 2000005

long A, B;
FILE *f, *g;

int C[NMax], rest[NMax], x;
int up[NMax], cif[NMax];
int in=1, sf=1;

void citire();
void rez();
long cmmdc( long A, long B );

void scrie(int k)
{
	// vreau sa scriu cifrele in ordine inversa.
	// deci tre sa scrie cifra de la k dupa ce au fost scrise cele dinainte...


	if (k)
	{
		scrie(up[k]);

		fprintf(g, "%d", cif[k]);
	}
}

int main()
{
	citire();
	rez();
	return 0;
}
void rez()
{
	int i, n, x1, x2;
	long M = A*B /cmmdc( A, B );

	C[1] = 1; rest[1] = cif[1] = 1;
	while ( !rest[0] && in <= sf )
	{
		x = C[in];

		x1 = (x*10)%M;

		if ( rest[x1] == 0 )
		{
			C[++sf]  = x1;
			rest[x1] = sf;
			cif[sf]	 = 0;
			up[sf]	 = in;
		}

		x2 = (x*10+1)%M;
		if ( rest[x2] == 0)
		{
			C[++sf]  = x2;
			rest[x2] = sf;
			cif[sf]	 = 1;
			up[sf]	 = in;
		}

		++in;
	}

	scrie(rest[0]);






/*
	n=0;
	pozb = rest[0];
	rest[0] = cif[pozb];
	n++;
	while ( up[pozb] )
	{
		rest[n] = cif[up[pozb]];
		up[pozb] = up[up[pozb]];
		n++;
	}
	rest[n] = 1;
	n++;
	
 	for (i=n-1; i>=0; i--)
 		fprintf( g, "%d", rest[i] );
*/

 	fprintf( g, "\n" );
}
long cmmdc( long A, long B )
{
	long R;
	while ( B )
	{
		R = A % B;
		A = B;
		B = R;
	}
	return A;
}
void citire()
{
	f = fopen( "multiplu.in", "rt" );
	g = fopen( "multiplu.out", "wt" );

	fscanf( f, "%ld %ld", &A, &B );
	fclose( f );
}