Cod sursa(job #248576)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 26 ianuarie 2009 00:56:44
Problema Multiplu Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
using namespace std;
bool viz[1<<21];
int que[1<<21];


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

#include <bitset>

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]] = 1;
	viz[1] = true;
	
	for(int i=1;i<=que[0];++i)
	{
		int x = que[i];
		if(!(x%M))
		{	
			printf("%d\n",x);
			exit(0);
		}	
		if(!viz[(x * 10) % M])
		{
			viz[(x * 10) % M] = true;
			que[++que[0]] = x * 10;
		}
		if(!viz[(x * 10 + 1) % M])
		{
			viz[(x * 10 + 1) % M] = true;
			que[++que[0]] = x * 10 + 1;
		}
	}
	
	printf("non_bulan");
	return 0;
}