Cod sursa(job #3240440)

Utilizator PescarusTanislav Luca Andrei Pescarus Data 15 august 2024 14:15:52
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream>
#include <queue>
using namespace std;
ifstream f("multiplu.in");
ofstream g("multiplu.out");
const int nmax = 2000005;

queue<int> q; //coada de resturi

int prv[nmax];
bool viz[nmax];
int n, a, b;
int cmmdc(int x, int y){
    while(y != 0){
        int r = x % y;
        x = y;
        y = r;
    }
    return x;
}

void reconst(int rest){
    if(rest == 1){
        g << 1;
        return;
    }
    reconst(prv[rest]);
    int nr = prv[rest];
    if((nr * 10 + 1) % n == rest){
        //avem 1
        g << 1;
    } else{
        //avem 0
        g << 0;
    }
}
int main(){
    f >> a >> b;
    n = a * b / cmmdc(a, b);
    if(n == 1){
        g << 1;
        return 0;
    }
    q.push(1);
    prv[1] = 0;
    viz[1] = true;
    while(!q.empty()){
        int rest = q.front();
        q.pop();
        int next_rest = (rest * 10) % n;
        if(viz[next_rest] == 0){
            q.push(next_rest);
            prv[next_rest] = rest;
            viz[next_rest] = true;
        }
        if(next_rest == 0){
            break;
        }
        next_rest = (rest * 10 + 1) % n;
        if(viz[next_rest] == 0){
            q.push(next_rest);
            prv[next_rest] = rest;
            viz[next_rest] = true;
        }
        if(next_rest == 0){
            break;
        }
    }
    reconst(0);
}