Cod sursa(job #115348)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 16 decembrie 2007 12:14:40
Problema Multiplu Scor 30
Compilator cpp Status done
Runda preONI 2008, Runda 2, Clasele 11-12 Marime 1.33 kb
#include <stdio.h>
#include <string.h>

#define MAXL 32
#define logBAZA 8
#define BAZA 100000000
#define OUTPUT_FORMAT "%08d"

const int put10[ logBAZA ] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000};

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; long long t = 0;
	for (i = A[0]; i > 0; i--)
		t = (t * BAZA + A[i]) % B;
	return t;
}

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

inline void set1( int poz ) { poz--; cur[ (poz >> 3) + 1 ] += put10[ poz & 7 ]; }
inline void set0( int poz ) { poz--; cur[ (poz >> 3) + 1 ] -= put10[ poz & 7 ]; }

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

		print(cur);
		return 1;
	}

	if (back( k - 1 ))
		return 1;
	set1(k);
	if (back( k - 1 ))
		return 1;
	set0(k);
	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++)
	{
		memset( cur, 0, sizeof(cur) );

		cur[0] = len;
		set1(len);

		for (; cur[0] > 1 && !cur[ cur[0] ]; cur[0]--);

		if (back( len - 1 ))
			return 0;
	}
	return 0;
}