Cod sursa(job #116189)

Utilizator sandyxpSanduleac Dan sandyxp Data 17 decembrie 2007 22:15:41
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <iostream>

#define FIN "multiplu.in"
#define FOUT "multiplu.out"
#define MAXM 2000000

struct item {
    int rem, prev; char lastbit;
} C[MAXM];
int Used[MAXM];

void callme(int b) {
    if (b) callme(C[b].prev);
    printf("%c", C[b].lastbit);
}

int cmmdc(int a, int b) {
    while (a && b) {
        if (a>b) a %= b;
        else b %= a;
    }
    return a | b;
}

int main()
{
    int a, b, p, u;
    freopen(FIN, "r", stdin);
    freopen(FOUT,"w",stdout);
    scanf("%d %d", &a, &b);
    a = a*b / cmmdc(a, b);
    p = u = 0;
    C[u++] = (item) { 1, 0, '1' }; // 1 % a
    Used[1] = 1;
    for (;; ++p) {
        if (!Used[b=(C[p].rem * 10) % a]) {
            C[u++] = (item) { b, p, '0' };
            Used[b] = 1;
        }
        if (b == 0) break;
        if (!Used[b=(C[p].rem * 10 + 1) % a]) {
            C[u++] = (item) { b, p, '1' };
            Used[b] = 1;
        }
        if (b == 0) break;
    }
    callme(u-1);
    printf("\n");
    return 0;
}