Cod sursa(job #188582)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 9 mai 2008 08:02:01
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<stdio.h>
#define N 2000005
int v[N],c[N],pred[N];
int a,b;
int gcd(int a,int b){
	int r=a%b;
	while(r){
		a=b;
		b=r;
		r=a%b;
	}
	return b;
}
void write(int x){
	if(pred[x]>=0)
		write(pred[x]);
	printf("%d",v[x]);
}
int main(){
	long k;
	int i,p,u,r=1;
	freopen("multiplu.in","r",stdin);
	freopen("multiplu.out","w",stdout);
	scanf("%d",&a);
	scanf("%d",&b);
	k=a*b/gcd(a,b);
	for(i=0;i<k;++i)
		v[i]=-1;
	p=u=0;
	c[p]=1;
	v[1]=1;
	pred[1]=-1;
	while(p<=u){
		r=c[p]*10%k;
		if(v[r]==-1){
			v[r]=0;
			pred[r]=c[p];
			c[++u]=r;
			if(r==0){
				write(r);
				printf("\n");
				return 0;
			}
		}
		r=(c[p]*10+1)%k;
		if(v[r]==-1){
			v[r]=1;
			pred[r]=c[p];
			c[++u]=r;
			if(r==0){
				write(r);
				printf("\n");
				return 0;
			}
		}
		++p;
	}
	return 0;
}