Cod sursa(job #3365350)

Utilizator AsarguSargu Alexandru Asargu Data 19 septembrie 2026 20:50:20
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <bits/stdc++.h>

#define ll long long
#define ull unsigned ll
//#define int long long

using namespace std;
using i128 = __int128;

ifstream fin("multiplu.in");
ofstream fout("multiplu.out");

const int NMAX = 2e6;

int a, b, m;
bool visited[NMAX + 1];
int parent[NMAX + 1];
int digit[NMAX + 1];

int gcd_(int x, int y) {
    while(y) {
        int r = x % y;
        x = y;
        y = r;
    }
    return x;
}

int lcm_(int x, int y) {
    return x / gcd_(x, y) * y;
}

void BFS() {
    queue<int> q;
    q.push(1);
    visited[1] = true;
    parent[1] = -1;
    int lcm = lcm_(a, b);

    while(!q.empty()) {
        auto current_rest = q.front();
        q.pop();

        if(current_rest == 0) {
            return;
        }

        for(int c = 0; c <= 1; c++) {
            int new_rest = (current_rest * 10 + c) % lcm;

            if(!visited[new_rest]) {
                visited[new_rest] = true;
                parent[new_rest] = current_rest;
                digit[new_rest] = c;
                q.push(new_rest);
            }
        }
    }
}

void backtrack_path(int current_rest) {
    if(parent[current_rest] == -1) {
        fout << 1;
        return;
    }
    backtrack_path(parent[current_rest]);
    fout << digit[current_rest];
}

int main() {
    fin >> a >> b;
    BFS();

    backtrack_path(0);

    return 0;
}