Cod sursa(job #3300776)

Utilizator ifrimdragosIfrim Dragos ifrimdragos Data 18 iunie 2025 22:46:27
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

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

const int xmax=2000005;

int cmmdc(int a,int b)
{
    if(a>b)
    {
        while(a%b!=0)
        {
            int aux=a%b;
            a=b;
            b=aux;
        }
        return b;
    }
     else if(a<=b)
    {
        while(b%a!=0)
        {
            int aux=b%a;
           b=a;
           a=aux;
        }
        return a;
    }
}
queue<int> q;
int previ[xmax];
int x;
void recon(int r)
{

    if(r==1)
    {
        fout<<'1';
        return;
    }
    int rest = previ[r];
    recon(rest);
    if((rest*10)%x == r)
        {
            fout<<'0';
        }
    else if ((rest*10 + 1)%x == r)
        {
            fout<<'1';
        }


}


int main()
{
    for(int i=0;i<xmax;++i)
    {
        previ[i]=-1;
    }

    previ[1]=1;
    int a,b;
    fin>>a>>b;
    x=a*b/cmmdc(a,b);
    int r =1 ;
    q.push(r);
    while(!q.empty())
    {
        r = q.front();
        q.pop();
        if(r==0)
        {
            break;
        }
        int rest0 = (r*10)%x;
        if(previ[rest0]==-1)
        {
            previ[rest0]=r;
            q.push(rest0);
        }
        int rest1 = (r*10+1)%x;
        if(previ[rest1]==-1)
        {
            previ[rest1] = r;
            q.push(rest1);
        }

    }




    recon(0);


    return 0;
}