Cod sursa(job #115274)

Utilizator raula_sanChis Raoul raula_san Data 16 decembrie 2007 11:55:20
Problema Multiplu Scor 10
Compilator cpp Status done
Runda preONI 2008, Runda 2, Clasele 11-12 Marime 0.76 kb
#include <cstdio>
#include <cstring>

int A, B, M;

int X[1024], Bit[1024];

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

int rest(int V[], int v)
{
	int i, r = 0;
	
	for(i=V[0]; i; --i)
	{
		r = r * 10 + V[i];
		r %= v;
	}
	
	return r;
}

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

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

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

	int i, j, k;
	
	for(j=1; ; ++j)
	{
		k = j;
		memset(Bit, 0, sizeof(Bit));

		while(k)
		{
			Bit[++Bit[0]] = k & 1;
			k >>= 1;
		}

		if(!rest(Bit, M))
		{
			for(k=Bit[0]; k; --k)
				printf("%d", Bit[k]);

			break;
		}
	}

	fclose(stdin);
	fclose(stdout);
	return 0;
}