Cod sursa(job #1551761)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 16 decembrie 2015 16:33:02
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <cstdio>

using namespace std;

#define MaxN 2000000

int Q[MaxN];
int qStart, qEnd;

int numDigs[MaxN];
int father[MaxN];
bool digit[MaxN];

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

void print(const int rest) {
    if (numDigs[rest] > 1) {
        print(father[rest]);
    }
    putchar(digit[rest] + '0');
}

int main(void) {
    freopen("multiplu.in", "r", stdin);
    freopen("multiplu.out", "w", stdout);
    int A, B;

    scanf("%d%d", &A, &B);
    fclose(stdin);

    A = (A * B) / gcd(A, B);

    if (A == 1) {
        putchar('1');
        fclose(stdout);
        return 0;
    }

    numDigs[1] = 1;
    digit[1] = 1;
    Q[0] = 1;
    qStart = 0;
    qEnd = 1;

    while (qStart < qEnd && !numDigs[0]) {
        const int restCurr = Q[qStart++];
        for (int i = 0; i <= 1; i++) {
            const int restNou = (restCurr * 10 + i) % A;
            if (!numDigs[restNou]) {
                numDigs[restNou] = numDigs[restCurr] + 1;
                father[restNou] = restCurr;
                digit[restNou] = i;
                Q[qEnd++] = restNou;
            }
        }
    }

    print(0);
    fclose(stdout);
    return 0;
}