Cod sursa(job #115672)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 16 decembrie 2007 19:57:21
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <cstdio>
#include <queue>

using namespace std;

#define MAXN 2000005

int A, B, M;
char seen[MAXN]; int p[MAXN];

queue<int> Q;

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

inline void genSol( int k )
{
	if (k == 1) { printf("1"); return; }
	genSol( p[k] );

	if ((p[k] * 10) % M == k)
		printf("0");
	else
		printf("1");
}

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

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

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

	seen[1] = 1;
	for (Q.push(1); !Q.empty(); Q.pop())
	{
		int i = Q.front(), newi;

		if (i == 0)
		{
			genSol(i);
			printf("\n");
			return 0;
		}

		newi = (i * 10) % M;
		if (!seen[newi])
			seen[newi] = 1,
			p[newi] = i,
			Q.push( newi );

		newi = (i * 10 + 1) % M;
		if (!seen[newi])
			seen[newi] = 1,
			p[newi] = i,
			Q.push( newi );
	}

	return 0;
}