Cod sursa(job #3259139)

Utilizator vladsoartavlad sofronea vladsoarta Data 25 noiembrie 2024 11:26:00
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
ifstream cin("multiplu.in");
ofstream cout("multiplu.out");

int cmmmc;
int restwithprevrest[2000001];
queue<int>q;

void construct(int rest){

    if(rest == 1)
    {cout<<'1';
        return;
    }

    int comefromrest = restwithprevrest[rest];
    construct(comefromrest);

    if((comefromrest*10)%cmmmc == rest)
        cout<<'0';
    else
        cout<<'1';

}

int main()
{
    int a,b;
    cin>>a>>b;

    cmmmc = a*b/__gcd(a,b);


    for(int i=0;i<cmmmc;i++)
        restwithprevrest[i]=-1;

    q.push(1);
    while(!q.empty()){
        int r=q.front();
        q.pop();

        if(r==0)
            break;

        int r0 = (r*10)%cmmmc;
        if(restwithprevrest[r0] == -1)
        {
            restwithprevrest[r0] = r;
            q.push(r0);
        }

        int r1 = (r*10+1)%cmmmc;
        if(restwithprevrest[r1] == -1)
        {
            restwithprevrest[r1] = r;
            q.push(r1);
        }
    }

    construct(0);

    return 0;
}