Cod sursa(job #579106)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 11 aprilie 2011 20:56:48
Problema Multiplu Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <fstream.h>
ifstream f("multiplu.in");
ofstream g("multiplu.out");
long a,b;
long c[101],viz[101],t[101],v[101];

long cmmdc(long x,long y){
	long r;
	while(y!=0){
		r=x%y;
		x=y;
		y=r;
	}
	return x;
}

long cmmmc(long x,long y){
	return x*y/cmmdc(x,y);
}

void drum(long u){
	if(u!=0){
		drum(t[u]);
		g<<v[u];
	}
}

int main(void){
	register int i,j,ok=0;

	f>>a>>b;
	long x=cmmmc(a,b);

	long p=1,u=1,r;
	c[p]=1;
	v[1]=1;
	while(p<=u){
		for(i=0;i<=1;i++){
			r=(c[p]*10+i)%x;

			if(!viz[r]){
				c[++u]=r;
				t[u]=p;
				v[u]=i;
				viz[r]=1;
				if(!r){
					ok=1;
					break;
				}
			}
		}
		if(ok)
			break;
		p++;
	}

	drum(u);
	f.close();
	g.close();
	return 0;
}