Cod sursa(job #3166617)

Utilizator Cristi3956Pop Cristian Cristi3956 Data 9 noiembrie 2023 09:36:10
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
int a,b,m,rc,urm;
queue<int> q;
int main()
{
    fin>>a>>b;
    m=(a*b)/__gcd(a,b);
    vector<bool> u(m,false);
    vector<int> p(m),c(m);
    q.push(1);
    u[1]=true;
    p[1]=-1;
    c[1]=1;
    while(!q.empty())
    {
        rc=q.front();
        q.pop();
        if(rc==0)
        {
            vector<int> sol;
            for(int i=0;rc!=-1;rc=p[rc])
                sol.push_back(c[rc]);
            for(int i=sol.size()-1;i>=0;i--)
                fout<<sol[i];
            fout<<'\n';
            break;
        }
        for(int i:{0,1})
        {
            urm=(rc*10+i)%m;
            if(!u[urm])
            {
                q.push(urm);
                u[urm]=true;
                p[urm]=rc;
                c[urm]=i;
            }
        }
    }
    return 0;
}