Cod sursa(job #115116)

Utilizator damaDamaschin Mihai dama Data 16 decembrie 2007 10:57:54
Problema Multiplu Scor 30
Compilator cpp Status done
Runda preONI 2008, Runda 2, Clasa a 10-a Marime 0.81 kb
#include <stdio.h>


int c, t = 1, maxlen, ok, v[30], rest[30];

int cmmdc(int, int);
void bkt(int);

int main()
{
	freopen("multiplu.in", "r", stdin);
	freopen("multiplu.out", "w", stdout);

	int a, b, i;

	scanf("%d %d", &a, &b);

	c = (a * b) / cmmdc(a, b);
	for(i = 1; i <= 30; ++i)
	{
		rest[i] = (10 * rest[i - 1] + 1) % c;
	}
	v[1] = 1;
	for(maxlen = 1; maxlen <= 30 && !ok; ++maxlen)
	{
		bkt(2);
	}

	return 0;
}

void bkt(int k)
{
	if(k == maxlen + 1)
	{
		if(t % c == 0)
		{
			for(int i = 1; i <= maxlen; ++i)
			{
				printf("%d", v[i]);
			}
			printf("\n");
			ok = 1;
		}
	}
	else
	{
		if(!ok)
		{
			int oldt = t;
			t *= 10;
			t %= c;
			bkt(k + 1);
			t += 1;
			v[k] = 1;
			bkt(k + 1);
			t = oldt;
			v[k] = 0;
		}
	}
}

int cmmdc(int a, int b)
{
	if(a % b == 0)
	{
		return b;
	}
	return cmmdc(b, a % b);
}