Cod sursa(job #117060)

Utilizator raula_sanChis Raoul raula_san Data 20 decembrie 2007 15:48:00
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>
#include <bitset>
#include <vector>

#define dim 2000001

using namespace std;

int A;
int B;
int M;
int P;
int U;

int Cb[dim];
int Cp[dim];
int Cr[dim];

vector <int> V;

bitset <dim> Used;

int Euclid(int x, int y)
{
	int r;
	
	while(y)
	{
		r = x % y;
		x = y;
		y = r;
	}
	return x;
}

void Rec(int pos)
{
	while(pos)
	{
		V.push_back(Cb[pos]);
		pos = Cp[pos];
	}
}

int main()
{
	freopen("multiplu.in", "rt", stdin);
	freopen("multiplu.out", "wt", stdout);
	
	scanf("%d %d", &A, &B);
	
	M = (A * B) / Euclid(A, B);

	P = 1;
	U = 1;
	
	Cb[1] = 1;
	Cr[1] = 1 % M;
	
	Used[1 % M] = 1;
	
	int r, r1, r2;
	
	while(P <= U)
	{
		r = Cr[P];
		
		r1 = r * 10;
		r2 = r * 10 + 1;
		
		r1 %= M;
		r2 %= M;
		
		if(!Used[r1])
		{
			++ U;
			
			Cb[U] = 0;
			Cp[U] = P;
			Cr[U] = r1;
			
			Used[r1] = 1;
		}
		
		if(!r1)
		{
			Rec(U);
			break;
		}
		
		if(!Used[r2])
		{
			++ U;
			
			Cb[U] = 1;
			Cp[U] = P;
			Cr[U] = r2;
			
			Used[r2] = 1;
		}
		
		if(!r2)
		{
			Rec(U);
			break;
		}
		
		++ P;
	}
	
	int i, n;
	
	n = V.size();
	
	for(i=n-1; i>=0; --i)
		printf("%d", V[i]);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}