Cod sursa(job #115227)

Utilizator MarquiseMarquise Marquise Data 16 decembrie 2007 11:45:42
Problema Multiplu Scor 10
Compilator cpp Status done
Runda preONI 2008, Runda 2, Clasa a 10-a Marime 1.34 kb
#include <stdio.h>
#define NMAX 100000000000000000LL
#include <math.h>
int a, b, n;
int x[1000];

int cmmdc(int u, int v)
{
	int k, dif, m = 0;
	if ( u == 0 || v == 0)
		return u|v;
	for ( k = 0; ( (u|v)&1 )==0; k++)
	{
		u>>=1;
		v>>=1;
	}
	while ( (u&1) == 0)
		u>>=1;
	do
	{
		while ( ( v&1) == 0 )
			v>>=1;
		if ( u <= v)
			v = v - u;
		else
		{
			dif = u - v;
			u = v;
			v = dif;
		}
	}while (v);
	m = m | (1<<k);
	return m * u;
}

int rest(int a[], int b)
{
	int i, t = 0;
	for ( i = a[0]; i >0; i--)
		t = (t *10+a[i])%b;
	return t;
}

int verific(long long k)
{
	int c;
	while ( k )
	{
		c = k % 10;
		if ( !(c == 0 || c == 1) )
			return 0;
		k /=10;
	}
	return 1;
}

int main()
{
	int c, m, r, j, ex = 1;
	long long k, i, l;
	freopen("multiplu.in", "r", stdin);
	freopen("multiplu.out", "w", stdout);
	scanf("%d %d", &a, &b);
	c = cmmdc(a,b);
	m = (a*b) / c;
	n = log10(m) + 1;
	l = NMAX / m;

		for ( i = 2; i <= l && ex; i++)
		{
			k = i * m;
			if ( verific(k))
				printf("%d", k), ex = 0;
		}

	if (ex)
	{
		for ( i = 1; i <= n; i++)
			x[i] = 1;
		x[0] = n;
		for ( i = n + 1; i <= m && ex; i++)
		{
			x[0]++;
			x[x[0]] = 1;
			r = rest(x, m);
			if ( r == 0)
			{
				for ( j = 1; j <= i; j++)
					printf("1");
				ex = 0;
			}

		}
	}

	return 0;
}