Cod sursa(job #118278)

Utilizator MarquiseMarquise Marquise Data 24 decembrie 2007 02:32:56
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <stdio.h>
#define NMAX 2000000
int a, b, m, c;
char  viz[250000];
typedef struct
{
    char c;
    int r, p;
}QUADA;
QUADA q[NMAX];

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;
}



void afisare(int i)
{
    if (i!=0)
    {
        afisare(q[i].p);
        printf("%c",q[i].c);
    }
}

void rezolv()
{
    int st, dr, ex = 1, r;
    st = dr = 1;
    q[st].c = '1';
    q[st].p = 0;
    q[st].r = 1 % m;
    viz[q[st].r>>3] |=(1<<(q[st].r&7));
    while ( st <= dr && ex)
    {
        r = (q[st].r*10 ) % m;
        if ( !(viz[r>>3] & (1<<(r&7)) ) )
        {
            dr++;
            q[dr].r = r;
            q[dr].p = st;
            q[dr].c = '0';
            viz[q[dr].r>>3] |= 1<<(q[dr].r&7);
            if (q[dr].r == 0)
               ex = 0;
        }
        if ( ex)
        {
        r = (q[st].r*10 + 1) % m;
        if ( !(viz[r>>3] & (1<<(r&7)) ) )
        {
            dr++;
            q[dr].r = r;
            q[dr].p = st;
            q[dr].c = '1';
            viz[q[dr].r>>3] |= 1<<(q[dr].r&7);
            if (q[dr].r == 0)
               ex = 0;
        }
        }
        st++;
    }

    if ( !ex)
       afisare(dr);


}


int main()
{
    freopen("multiplu.in", "r", stdin);
    freopen("multiplu.out", "w", stdout);
    scanf("%d %d", &a, &b);
    c = cmmdc(a,b);
    m = (a*b)/c;
    rezolv();
    return 0;
}