Cod sursa(job #113272)

Utilizator filipbFilip Cristian Buruiana filipb Data 9 decembrie 2007 14:24:31
Problema Multiplu Scor Ascuns
Compilator cpp Status done
Runda Marime 0.98 kb
#include <stdio.h>
#define NMax 2000005

int M, A, B;
int q[NMax], up[NMax];
char digit[NMax], uz[NMax];

int gcd(int A, int B)
{
    if (B == 0) return A;
    return gcd(B, A % B);
}

int main(void)
{
    int i, ql = 0, qr = 0, x;
    
    freopen("multiplu.in", "r", stdin);
    freopen("multiplu.out", "w", stdout);

    scanf("%d %d", &A, &B);
    if (A * B > 2000000)
	for (;;);
    M = A * B / gcd(A, B);

    for (q[0]=1, digit[0] = 1, up[0]=-1, uz[1] = 1; qr <= ql; qr++)
    {
        x = (q[qr] * 10) % M;
        if (!uz[x])
            q[++ql] = x, uz[x] = 1, up[ql] = qr, digit[ql] = 0;

        x = (q[qr] * 10 + 1) % M;
        if (!uz[x])
            q[++ql] = x, uz[x] = 1, up[ql] = qr, digit[ql] = 1;

        if (uz[0])
            break;
    }


    for (x = ql - (q[ql] != 0), ql = 0; x != -1; x = up[x])
        q[++ql] = (int)digit[x];

    for (i = ql; i >= 1; i--)
        printf("%d", q[i]);
    printf("\n");

    return 0;
}