Cod sursa(job #1211433)

Utilizator BLz0rDospra Cristian BLz0r Data 22 iulie 2014 16:31:29
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <cstdio>
using namespace std;

FILE *f=fopen ("multiplu.in","r");
FILE *g=fopen ("multiplu.out","w");

int up[2000002],q[2000002];;
bool ap[2000002],cif[2000002];

int cmmmc (int a, int b){
	int r=1,prod=a*b;
	while (r!=0){
		r=a%b;
		a=b;
		b=r;
	}
	return prod/a;
}

void remake (int x){
	if (x==0) return;
	remake (up[x]);
	fprintf (g,"%d",cif[x]);
}

int main(){
	int a,b,x,L=1;
	
	fscanf (f,"%d%d",&a,&b);
	
	x=cmmmc (a,b);
	q[1]=1; ap[1]=1; cif[1]=1;
	
	for (int i=1;i<=L;++i){
		if (!ap[q[i]*10%x]){
			q[++L]=q[i]*10%x;
			ap[q[i]*10%x]=1;
			cif[L]=0;
			up[L]=i;
		}
		if (!ap[(q[i]*10+1)%x]){
			q[++L]=(q[i]*10+1)%x;
			ap[(q[i]*10+1)%x]=1;
			cif[L]=1;
			up[L]=i;
		}
		if (ap[0]){
			remake (L);
			break;
		}
	}
	
	return 0;
}