Cod sursa(job #2978157)

Utilizator popescuadrianpopescuadrian popescuadrian Data 13 februarie 2023 10:24:43
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
ifstream cin("multiplu.in");
ofstream cout("multiplu.out");
long long mod=666013;
int viz[2000005];
int sol[2000005];
int par[2000005];
vector<int>vec;
queue<int>qu;
int main()
{
    int n,i,j,k,l,x,nr,suma=0,a,b,prod,curr;
    cin>>a>>b;
    prod=a*b/__gcd(a,b);
    viz[1]=1;
    sol[1]=1;
    qu.push(1);
    while(qu.size())
    {
        curr=qu.front();
        qu.pop();
        if(viz[(curr*10)%prod]==0)
        {
            sol[(curr*10)%prod]=0;
            viz[(curr*10)%prod]=1;
            par[(curr*10)%prod]=curr;
            qu.push((curr*10)%prod);
        }
        if(viz[(curr*10+1)%prod]==0)
        {
            sol[(curr*10+1)%prod]=1;
            viz[(curr*10+1)%prod]=1;
            par[(curr*10+1)%prod]=curr;
            qu.push((curr*10+1)%prod);
        }
    }
    curr=0;
    while(curr!=1)
    {
        vec.push_back(sol[curr]);
        curr=par[curr];
    }
    vec.push_back(1);
    for(i=vec.size()-1;i>=0;i--)
    {
        cout<<vec[i];
    }
    return 0;
}