Cod sursa(job #2976163)

Utilizator SerbanCaroleSerban Carole SerbanCarole Data 8 februarie 2023 15:28:23
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>
#include <algorithm>
#include <bitset>
#include <queue>
using namespace std;

ifstream cin("multiplu.in");
ofstream cout("multiplu.out");

int a , b , m , x;

const int MAX = 2e6 + 1;

int pre[MAX];

bitset <MAX> cif , viz;

queue<int>q;

void rec( int x ){

    if(!pre[x]);
    else rec(pre[x]);

    cout << cif[x];
}

int main(){

    cin >> a >> b;

    m = a*b/__gcd(a,b);

    q.push(1);

    viz[1] = 1;

    cif[1] = 1;

    while(!q.empty()){

        x = q.front();

        q.pop();

        if(!x){

            rec(x);

            exit(0);
        }

        if(!viz[(x*10)%m]){

            viz[(x*10)%m] = 1;

            pre[(x*10)%m] = x;

            cif[(x*10)%m] = 0;

            q.push((x*10)%m);
        }

        if(!viz[(x*10+1)%m]){

            viz[(x*10+1)%m] = 1;

            pre[(x*10+1)%m] = x;

            cif[(x*10+1)%m] = 1;

            q.push((x*10+1)%m);
        }
    }

    return 0;
}