Cod sursa(job #926672)

Utilizator Sanduleac_VladSanduleac Vllad Alexandru Sanduleac_Vlad Data 25 martie 2013 12:19:07
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <stdio.h>

struct L {
    long c, r, t;
};

long a, b, m;
L q[1000001];
long r[2000001];

long bt(long i) {
    if(i == 1)
        return q[i].c;
    printf("%ld", bt(q[i].t));
    return q[i].c;
}

int main() {
    long i, j, x;
    L tmp;
    freopen("multiplu.in", "r", stdin);
    freopen("multiplu.out", "w", stdout);
    scanf("%ld %ld", &a, &b);
    i = a;
    j = b;
    while(b) {
        x = a % b;
        a = b;
        b = x;
    }
    m = i * j / a;
    tmp.c = 1;
    tmp.r = 1;
    tmp.t = 0;
    r[1] = 1;
    q[1] = tmp;
    j = 1;
    for(i = 1; q[i].r != 0; i++) {
        if(!r[(q[i].r * 10) % m]) {
            r[(q[i].r * 10) % m] = 1;
            q[++j].r = (q[i].r * 10) % m;
            q[j].c = 0;
            q[j].t = i;
        }
        if(!r[(q[i].r * 10 + 1) % m]) {
            r[(q[i].r * 10 + 1) % m] = 1;
            q[++j].r = (q[i].r * 10 + 1) % m;
            q[j].c = 1;
            q[j].t = i;
        }
    }
    printf("%ld\n", bt(i));
    return 0;
}