Cod sursa(job #115170)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 16 decembrie 2007 11:19:14
Problema Multiplu Scor 30
Compilator cpp Status done
Runda preONI 2008, Runda 2, Clasele 11-12 Marime 0.72 kb
#include <cstdio>

#define fin  "multiplu.in"
#define fout "multiplu.out"

int A,B,C;
int x[30],ret[30],dim=100;

int gcd(int a,int b)
{
	if ( !b )
		return a;
	else
		return gcd(b,a%b);
}

void go(int lev,int rest)
{
	int i;

	if ( rest == 0 )
	{
		if ( lev < dim )
		{	
			dim = lev ;
			for ( i = 0 ; i < lev ; ++i )
				ret[i] = x[i];
		}
		return ;
	}
	
	if ( lev == 23 )
		return;
	else
	{
		x[lev]=0;
		go(lev+1,( rest * 10 ) % C);
		x[lev]=1;
		go(lev+1,( rest * 10 + 1 ) % C );
	}
}

int main()
{
	int i;

	freopen(fin,"r",stdin);
	freopen(fout,"w",stdout);

	scanf("%d%d",&A,&B);

	C = A*B / gcd(A,B);
	
//	printf("%d\n",C);

	x[0]=1;

	go(1,1);

	for ( i = 0; i < dim ; ++i )
		printf("%d",ret[i]);
	printf("\n");

	return 0;
}