Cod sursa(job #2651875)

Utilizator ioana.jianuIoana Jianu ioana.jianu Data 23 septembrie 2020 18:47:17
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <iostream>
#include <stdio.h>

using namespace std;

const int MMAX = 2000005;
int q[MMAX];
struct elem{int prov, cf;};
elem r[MMAX];

int cmmdc (int a, int b) {
    int r;
    while (b > 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

void afis(int x) {
    if (r[x].prov != 0)
        afis (r[x].prov);
    printf ("%d", r[x].cf);
}

int main() {

    freopen ("multiplu.in", "r", stdin);
    freopen ("multiplu.out", "w", stdout);

    int a, b, m, x, st, dr;

    scanf ("%d%d", &a, &b);
    m = a * b / cmmdc(a, b);

    q[1] = 1;
    r[1].cf = 1;
    st = dr = 1;
    while (r[0].prov == 0) {
        x = q[st] * 10 % m;
        if (r[x].prov == 0 && x != 1) {
            r[x].prov = q[st];
            r[x].cf = 0;
            q[++dr] = x;
        }
        x = (q[st] * 10 + 1) % m;
        if (r[x].prov == 0 && x != 1) {
            r[x].prov = q[st];
            r[x].cf = 1;
            q[++dr] = x;
        }
        st++;
    }
    afis(0);


    return 0;
}