Cod sursa(job #293398)

Utilizator n3msizN3msiz n3msiz Data 1 aprilie 2009 19:22:54
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<stdio.h>

int N,a,b,i,d,c,s,cmmmc,u,p,max,j,k, C[2000010], T[2000010], r, t, ok;
char V[2000010], sol[2000010], D[2000010];

int cmmdc(int a, int b){

	int r;
	while( b ){
		r = a % b;
		a = b;
		b = r;
	}
	
	return a;
}

int main(){
	
	FILE*f=fopen("multiplu.in","r");
	FILE*g=fopen("multiplu.out","w");
	fscanf(f,"%d %d",&a,&b);

	d = cmmdc(a, b);
	cmmmc = a * b / d;
	
	p = u = 1;
	C[u] = 1;
	V[1] = 1;
	T[1] = 0; //care e tata
	D[1] = 1; //ce cifra am adaugat
	ok = 1;
	
	while( p <= u && ok) {
		for(i = 0; i <= 1; i++){
			r = (C[p]*10 + i) % cmmmc;
			if( !V[r] ){
				u++;
				V[r] = 1;
				C[u] = r;
				T[u] = p;
				D[u] = i;
				
				if( r == 0 ){
					ok = 0;
					break;
				}
			}
		}
		
		p++;
	}
	
	t = u;
	while( t ){
		sol[++N] = D[t];
		t = T[t];
	}
	
	for(i = N; i >= 1; i--)
		fprintf(g,"%d",sol[i]);
	
	fclose(f);
	fclose(g);
	return 0;
}