Cod sursa(job #592418)

Utilizator CS-meStanca Marian Ciprian CS-me Data 28 mai 2011 12:25:42
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<stdio.h>
#define DIM 2000002
FILE *fin=fopen("multiplu.in","r");
FILE *fout=fopen("multiplu.out","w");
int a,b,x,r,viz[DIM],n,m,c[2][DIM],t[DIM],p,u,i,v[DIM];

int main(){

	fscanf(fin,"%d %d",&a,&b);
	n=a; m=b;

	while(b!=0){
		r=a%b;
		a=b;
		b=r;
		
	}
	
	x=m/a*n;
	
	p=1; u=1;
	c[0][1]=1;
	c[1][1]=1;
	t[1]=0;
	
	while(p<=u && c[0][u]!=0){
		for(i=0;i<=1;i++){
			n=(c[0][p]*10+i)%x;
			if( viz[n]==0 ){
				viz[n]=1;
				u++;
				c[0][u]=n;
				c[1][u]=i;
				t[u]=p;
				if(c[0][u]==0){
					break;
				}	
			}
		}
		p++;
	}
	
	v[0]=0;
	
	while(u!=0){
		v[0]++;
		v[v[0]]=c[1][u];
		u=t[u];
	}
	
	for(i=v[0];i>=1;i--){
		fprintf(fout,"%d",v[i]);
	}
	
return 0;
}