Cod sursa(job #2714307)

Utilizator darius2k2Floroiu Darius Eduard darius2k2 Data 1 martie 2021 17:48:18
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

queue <int> coada;

int pred[2000001], ultim[2000001];

int m;

void cmmmc()
{
    coada.push(1);
    pred[1]=-1;
    ultim[1]=1;
    while(!coada.empty()){
        int x=coada.front();
        coada.pop();
        for(int i=0;i<2;i++){
            int y=(x*10+i)%m;
            if(pred[y]==0){
                ultim[y]=i;
                pred[y]=x;
                if(y==0)
                    return;
                coada.push(y);
            }
        }
    }
}

void numar(int x)
{
    if(x==-1)
        return;
    numar(pred[x]);
    out<<ultim[x];
}

int main()
{
    int a,b,copa,copb,r;
    in>>a>>b;
    copa=a;
    copb=b;
    while(copb!=0){
        r=copa%copb;
        copa=copb;
        copb=r;
    }
    m=a*b/copa;
    cmmmc();
    numar(0);
    return 0;
}