Cod sursa(job #613597)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 1 octombrie 2011 14:54:53
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <stdio.h>
#define val 1000004
#define val1 2000004
int a , b , M , prod , r , k  , p , u , x , i;
int C[4][val];
int V[val];
int Fr[val1];
int main(){
	freopen("multiplu.in","r",stdin);
	freopen("multiplu.out","w",stdout);
	scanf("%d %d",&a , &b);
	prod=a*b;
	while(b!=0){
		r=a%b;
		a=b;
		b=r;
	}
	M=prod/a;
	C[1][1]=1%M;
	C[3][1]=1;
	p=1;u=1;
	while(p<=u){
		x=C[1][p]*10%M;
		if(Fr[x]==0){
			Fr[x]++;
			C[1][++u]=x;
			C[2][u]=p;
			C[3][u]=0;
			if(C[1][u]==0){
				break;
			}
		}
		x=(C[1][p]*10+1)%M;
		if(Fr[x]==0){
			Fr[x]++;
			C[1][++u]=(C[1][p]*10+1)%M;
			C[2][u]=p;
			C[3][u]=1;
			if(C[1][u]==0){
				break;
			}
		}
		p++;
	}
	while(u){
		V[++k]=C[3][u];
		u=C[2][u];
	}
	for(i=k;i>=1;i--){
		printf("%d",V[i]);
	}
	return 0;
}