Cod sursa(job #1850786)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 18 ianuarie 2017 22:01:34
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <iostream>
#include <cstdio>
#include <bitset>
#define MAXM 2000050

using namespace std;

int m;
int lis[MAXM], pre[MAXM], el[MAXM];
int nq = 0;

int cmmdc(int a, int b)
{
    if (b == 0) return a;
    return cmmdc(b, a % b);
}

void ad(int p, int nr, int ce)
{
    if (pre[nr]) return;
    pre[nr] = p;
    el[nr] = ce;
    lis[++nq] = nr;
}

int solve()
{
    pre[1] = -1;
    lis[++nq] = 1;
    el[1] = 1;
    for (int i = 1; i <= nq; i++) {
        int c1 = (lis[i]*10) % m;
        int c2 = (lis[i]*10 + 1) % m;
        ad(lis[i], c1, 0);
        ad(lis[i], c2, 1);
        if (!c1 || !c2)
            return 0;
    }
}

void afis(int pos)
{
    if (pre[pos] != -1)
        afis(pre[pos]);
    printf("%d", el[pos]);
}

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

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

    return 0;
}