Cod sursa(job #2785747)

Utilizator Albert_GAlbert G Albert_G Data 19 octombrie 2021 13:10:10
Problema Multiplu Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
#include <queue>

std::ifstream in("multiplu.in");
std::ofstream out("multiplu.out");

const int N = 2e6 + 1;
int previous[N], number[N];
bool digit[N];
int a, b, lcm;

int gcd(int a, int b){
    if(!b)
        return a;
    return gcd(b, a%b);
}

void choice(std::queue<int> &q, int currRest, bool d, bool &found){
    int newRest = (currRest * 10 + d) % lcm;
    if(previous[newRest] != 0) return;
    q.push(newRest);
    previous[newRest] = currRest;
    digit[newRest] = d;
    found = (newRest==0);
}

void bfs(){
    std::queue<int> q{{1}};
    digit[1] = 1;
    previous[1] = -1;
    bool found = false;
    while(!q.empty() && !found){
        int currRest = q.front();
        q.pop();
        choice(q, currRest, 0, found);
        choice(q, currRest, 1, found);
    }
}

int main(){
    in>>a>>b;
    lcm = a*b / gcd(a,b);
    int currRest = 0, cnt=0;
    bfs();
    while(currRest >= 0){
        number[cnt++] = digit[currRest];
        currRest = previous[currRest]; 
    }
    for(int i=cnt-1;i>=0;--i)
        out<<number[i];
}