Cod sursa(job #130668)

Utilizator marius135Dumitran Adrian Marius marius135 Data 1 februarie 2008 17:16:05
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<stdio.h>
#define maxn (1<<21)

long sol[maxn],ult[maxn];
char cif[maxn];
char sel[maxn];

long cmmdc(long a,long b)
{
	if( a<b ) a = b ^ a ^(b = a);
	while ( b)
	{
		long c = b;
		b = a % b;
		a = c;
	}
	return a;
}
void afisare(long a)
{
	if(a== 0) return;
	afisare(ult[a]);
	printf("%ld",(long) cif[a]);
	
}
int main()
{
	freopen("multiplu.in","r",stdin);
	//freopen("multiplu.out","w",stdout);

	long a,b,n;
	scanf("%ld %ld",&a,&b);
	n = a * b/ cmmdc(a,b);
	if( n == 1) {printf("%ld\n",1);return 0;}
	
	sol[1] = 1;
	ult[1] = 0;
	cif[1] = 1;
	long last = 1;
	long act = 0;
	
	while(++act)
	{
		long x;
		x = sol[act] *10 % n;
		if( sel[x] == 0)
		{
			sol[++last] = x;
			cif[last] = 0;
			ult[last] = act;
			if( x == 0)
				{afisare(last);return 0;}
			sel[x] =1 ;
		}
		x = (sol[act] *10 + 1) % n;
		if( sel[x] == 0)
		{
			sol[++last] = x;
			cif[last] = 1;
			ult[last] = act;
			if( x == 0)
				{afisare(last);return 0;}
			sel[x] =1 ;
		}
		
	}
	
	return 0;
}