Cod sursa(job #115270)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 16 decembrie 2007 11:55:02
Problema Multiplu Scor 20
Compilator cpp Status done
Runda preONI 2008, Runda 2, Clasa a 10-a Marime 0.88 kb
#include <stdio.h>

#define MAXL 32
#define BAZA 10000

int A, B, cmmmc, len;

inline int gcd( int A, int B )
{
	int C;
	for (; A % B; )
	{
		C = A % B;
		A = B;
		B = C;
	}
	return B;
}

int cur[MAXL];

inline int mod( int A[], int B )
{
	int i, t = 0;
	for (i = A[0]; i > 0; i--)
		t = (t * 10 + A[i]) % B;
	return t;
}

inline void print( int A[] )
{
	for (int i = A[0]; i >= 1; i--)
		printf("%d", A[i]);
	printf("\n");
}

int back( int k )
{
	if (k == 0)
	{
		if (mod(cur, cmmmc))
			return 0;

		print(cur);
		return 1;
	}

	cur[k] = 0;
	if (back( k - 1 ))
		return 1;
	cur[k] = 1;
	if (back( k - 1 ))
		return 1;
	return 0;
}

int main()
{
	freopen("multiplu.in", "rt", stdin);
	freopen("multiplu.out", "wt", stdout);

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

	cmmmc = A * B / gcd(A, B);

	for (len = 1; len <= 25; len++)
	{
		cur[0] = len; cur[len] = 1;
		if (back( len - 1 ))
			return 0;
	}
	return 0;
}