Cod sursa(job #3329387)

Utilizator tomavladnicolae@gmail.comTomavlad [email protected] Data 13 decembrie 2025 08:59:20
Problema Multiplu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <bits/stdc++.h>
using namespace std;

/**
C = 7
      1   2   3    4    5   6     7    8     9     10
q   = 1, 10, 11, 100, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101
q   = 1,  3  4    2    5    6     0
u   = 1   0  1    0    0     1    0
pred= 0   1  1    2    3     3    4

nr = 0001

1111111 - 1111 = 1110000

a % p = r
b % p = r
a-b diviz cu p

a = p*c1 + r
b = p*c2 + r

*/

ifstream fin("a.in");
ofstream fout("a.out");
int c[4];
bitset<2000001> fr;
int q[2000001], pr, ul;
bitset<2000001> u; /// ultima cifra
int pred[2000001];

void Afis(int k)
{
    string sol = "";
    while (k != 0)
    {
        if (u[k] == 0) sol = "0" + sol;
        else sol = "1" + sol;
        k = pred[k];
    }
    fout << sol << "\n";
}

int main()
{
    int a, b, c, k, poz;
    fin >> a >> b;
    if (a == 1 && b == 1)
    {
        fout << "1\n";
        return 0;
    }
    c = a * b / __gcd(a, b);
    /// cel mai mic numar cu cifre 0 si 1 care se imparte la c
    k = pr = ul = 1;
    q[1] = 1;
    fr[1] = 1;
    u[k] = 1;
    pred[k] = 0;
    while (1)
    {
        poz = pr;
        a = q[pr++];
        b = a * 10 % c;
        if (fr[b] == 0)
        {
            fr[b] = 1;
            q[++ul] = b;
            k++;
            u[k] = 0;
            pred[k] = poz;
        }
        if (b == 0)
        {
            Afis(k);
            return 0;
        }
        b = (a * 10 + 1) % c;
        if (fr[b] == 0)
        {
            fr[b] = 1;
            q[++ul] = b;
            k++;
            u[k] = 1;
            pred[k] = poz;
        }
        if (b == 0)
        {
            Afis(k);
            return 0;
        }
    }
    return 0;
}