Cod sursa(job #2913381)

Utilizator antonio_sefu_tauLaslau Antonio antonio_sefu_tau Data 14 iulie 2022 10:01:12
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
ifstream f("multiplu.in");
ofstream g("multiplu.out");
const int dim=2e6+5;
int a,b,prv[dim],c;
queue<int>q;
void reconst(int r){
    if(r==1){
        g<<1;
        return;
    }
    reconst(prv[r]);
    if(prv[r]*10%c==r)
        g<<0;
    else
        g<<1;
}
int main(){
    f>>a>>b;
    c=a*b/__gcd(a,b);
    for(int i=0;i<c;i++)
        prv[i]=-1;
    q.push(1);
    prv[1]=1;
    while(!q.empty()){
        int r=q.front();
        q.pop();
        if(!r)
            break;
        for(int i=0;i<=1;i++){
            int r0=(r*10+i)%c;
            if(prv[r0]==-1){
                prv[r0]=r;
                q.push(r0);
            }
        }
    }
    reconst(0);
    return 0;
}