Cod sursa(job #248588)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 26 ianuarie 2009 01:13:28
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
using namespace std;
bool viz[1<<21],L[1<<21];
int que[1<<21],poz[1<<21];

int gcd(int x, int y)  
{  
	for(int r;r;r=x%y,x=y,y=r);
	return x;  
} 

#include <bitset>

void print(int x)
{
	int stv[1<<15];
	for(;x;)
	{
		stv[++stv[0]] = L[x];
		x = poz[x];
	}
	for(int i=stv[0];i>=1;--i)
		printf("%d",stv[i]);	
}

int main()
{
	int A,B,M;
	
	freopen("multiplu.in","r",stdin);
	freopen("multiplu.out","w",stdout);
	
	scanf("%d %d",&A,&B);
	M = A*B / gcd(A,B); 
	
	que[++que[0]] = L[1] = 1;
	viz[1] = true;
	
	for(int i=1;i<=que[0];++i)
	{
		int rest = que[i];
		if(!rest)
		{	
			print(i);
			exit(0);
		}	
		if(!viz[(rest * 10) % M])
		{
			viz[(rest * 10) % M] = true;
			que[++que[0]] = (rest * 10) % M;
			L[que[0]] = 0;
			poz[que[0]] = i;
		}
		if(!viz[(rest * 10 + 1) % M])
		{
			viz[(rest * 10 + 1) % M] = true;
			que[++que[0]] = (rest * 10 + 1) % M;
			L[que[0]] = 1;
			poz[que[0]] = i;
		}
	}
	
	printf("non_bulan");
	return 0;
}