Cod sursa(job #3357274)

Utilizator ligmasigmaolimpiadaVlad Bratucu ligmasigmaolimpiada Data 7 iunie 2026 23:40:10
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>
#include <queue>
#include <string>
using namespace std;

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

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

int main(){
    int a, b;
    fin>>a>>b;
    int lcm=a/gcd(a,b)*b;
    vector<bool> viz(lcm, false);
    vector<int> parent(lcm, -1);
    vector<int> digit(lcm, -1);
    queue<int> q;
    int start=1%lcm;
    viz[start]=true;
    digit[start]=1;
    q.push(start);

    while(!q.empty()){
        int cur=q.front();
        q.pop();
        int r0 =(cur*10LL)%lcm;
        if(!viz[r0]){
            viz[r0]=true;
            parent[r0]=cur;
            digit[r0]=0;
            if(r0==0){
                q=queue<int>();
                break;
            }
            q.push(r0);
        }

        int r1=(cur*10LL+1)%lcm;
        if(!viz[r1]){
            viz[r1]=true;
            parent[r1]=cur;
            digit[r1]=1;
            if(r1==0){
                q=queue<int>();
                break;
            }
            q.push(r1);
        }
    }

    string r="";
    int cur=0;
    while(cur != -1){
        r = to_string(digit[cur])+r;
        cur=parent[cur];
    }

    fout<<r<<'\n';
    return 0;
}