Cod sursa(job #1822807)

Utilizator cyg_ieeuVasile Radu-Andrei cyg_ieeu Data 5 decembrie 2016 16:42:02
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <cstdio>

using namespace std;
const int nmax = 2000000;
struct mult
{
	int c,r,t;
};

mult q[nmax + 5];
bool fr[nmax + 5],sol[nmax + 5];
int cmmdc(int a,int b)
{
	int r;
	while(b)
	{
		r = a % b;
		a = b;
		b = r;
	}
	return a;
}
int main()
{
	freopen("multiplu.in", "r",stdin);
	freopen("multiplu.out", "w",stdout);
    int m,p,u,a,b,rn;
	scanf("%d%d", &a, &b);
	p = u = 1;
	mult temp;
	m = (a * b) / cmmdc(a,b);
	temp.c = temp.r = 1;
	temp.t = 0;
	fr[1] = 1;
	q[p] = temp;
	while(p <= u)
	{
		rn = (q[p].r * 10 + 0) % m;
		if(fr[rn] == 0)
		{
			fr[rn] = 1;
			temp.c = 0;
			temp.r = rn;
			temp.t = p;
			q[++u] = temp;
			if(rn == 0)
				break;
		}
		rn = (q[p].r * 10 + 1) % m;
		if(fr[rn] == 0)
		{
			fr[rn] = 1;
			temp.c = 1;
			temp.r = rn;
			temp.t = p;
			q[++u] = temp;
			if(rn == 0)
				break;
		}
		p++;
	}
	int k = 0,i;
	while(u)
	{
		sol[++k] = q[u].c;
		u = q[u].t;
	}
	for(i = k;i >= 1;i--)
		printf("%d",sol[i]);
    return 0;
}