Cod sursa(job #497966)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 3 noiembrie 2010 19:59:06
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<stdio.h>

#define dim 2000100

FILE*f=fopen("multiplu.in","r");
FILE*g=fopen("multiplu.out","w");

int p,u,A,B,pp,k,rst,i,fnd,rest[dim],T[dim];
char viz[dim],coada[dim],sol[dim];

inline void cmmmc () {
	int r;
	int produs = A * B;
	while ( B ){
		r = A % B;
		A = B;
		B = r;
	}
	pp = produs / A ; 
	
}

int main () {
	
	fscanf(f,"%d %d",&A,&B);
	
	cmmmc();
	coada[1] = 1;
	rest[1] = viz[1] = 1;
	p = u = 1;
	
	while ( p <= u && !fnd ){
		
		for ( i = 0 ; i <= 1 ; ++i ){
			rst = ( rest[p] * 10 + i ) % pp ;
			if ( !viz[rst] ){
				viz[rst] = 1;
				coada[++u] = i;
				rest[u] = rst;
				T[u] = p;
				if ( rst == 0 ){
					fnd = 1;
					break;
				}
			}
			
		}
		++p;
	}
	while ( u != 0 ){
		sol[++k] = coada[u];
		u = T[u];
	}
	
	for ( i = k ; i >= 1 ; --i )
		fprintf(g,"%d",sol[i]);
	
	fclose(f);
	fclose(g);
	
	return 0;
	
}