Cod sursa(job #810333)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 10 noiembrie 2012 09:54:33
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <stdio.h>
FILE *f=fopen("multiplu.in","r");
FILE *g=fopen("multiplu.out","w");
int A,B,M;
bool viz[2000011];

struct coada{
	int r;
	int c;
	int t;
};
coada C[2000011];

int cmmdc(int a,int b){
	int r;
	while(b!=0){
		r=a%b;
		a=b;
		b=r;
	}
	return a;
}

int cmmmc(int A,int B){
	return (A*B)/cmmdc(A,B);
}

void rec(int u){
	if(u>1)
		rec(C[u].t);
	fprintf(g,"%d",C[u].c);
}

int main(void){
	register int i,j;
	
	fscanf(f,"%d %d",&A,&B);
	
	//calculam cel mai mic multiplu comun
	M=cmmmc(A,B);
	
	int p=1,u=1;
	C[p].r=1;
	C[p].c=1;
	bool ok=false;
	viz[1]=1;
	while(p<=u){
		for(i=0;i<2;i++){
			if(!viz[(C[p].r*10+i)%M]){
				C[++u].r=(C[p].r*10+i)%M;
				viz[C[u].r]=true;
				C[u].c=i;
				C[u].t=p;
				if(C[u].r==0){
					ok=true;
					break;
				}
			}
		}
		if(ok)
			break;
		p++;
	}
	
	rec(u);
	fclose(f);
	fclose(g);
	return 0;
}