Cod sursa(job #522164)

Utilizator tangredonSilviu Georgescu tangredon Data 14 ianuarie 2011 14:27:41
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <iostream>
#include <fstream>
#include <string>
#define DIM 2000000
using namespace std;

ifstream f("multiplu.in");
ofstream g("multiplu.out");

int A, B, C, M;
int R[DIM];
int c[DIM];
int T[DIM];
char viz[DIM];
int ok;
int p, u, i;
char S[DIM];

int main ()
{
	f >> A >> B;
	M = A*B;
	while (B)
	{
		C = A%B;
		A = B;
		B = C;
	}
	M/=A;
	
	p = u = 1;
	R[1] = 1;
	c[1] = 1;
	viz[1] = 1;
	ok = 1;
	
	while ( ok )
	{
		for ( i = 0; i <= 1 ; i++ )
		{
			if ( viz[ (R[p]*10+i)%M ] == 0 )
			{
				u++;
				R[u] = (R[p]*10+i)%M;
				viz[ R[u] ] = 1;
				c[u] = i;
				T[u] = p;
				
				if ( R[u] == 0 )
				{
					ok = 0;
					break;
				}
			}
		}
		p++;
	}
	
	i = 0;
	while (u)
	{
		S[i++] = c[u] + '0';
		u = T[u];
	}
	S[i] = 0;
	strrev(S);
	g << S;
}