Cod sursa(job #3350021)

Utilizator SGLDCASA SI PODUL SGLD Data 4 aprilie 2026 19:55:03
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <iostream>
#include<vector>
#include<queue>
#include<bits/stdc++.h>
using namespace std;
ifstream in("multiplu.in");
ofstream out("multiplu.out");
int viz[2000001];
int drum[2000001];
int pref[2000001];
int cif[2000001];
int main()
{
    long long a,b;
    in>>a>>b;
    long long c=(a*b)/__gcd(a,b);
    queue<int> q;
    int start=1%c;
    q.push(start);
    viz[start]=1;
    cif[start]=1;
    while(!q.empty())
    {
        int pos=q.front();
        q.pop();
        if(pos==0)
        {
            break;
        }
        int nxt=(pos*10)%c;
        if(!viz[nxt])
        {
            viz[nxt]=1;
            q.push(nxt);
            pref[nxt]=pos;
            cif[nxt]=0;
        }
        nxt=(pos*10+1)%c;
        if(!viz[nxt])
        {
            viz[nxt]=1;
            q.push(nxt);
            pref[nxt]=pos;
            cif[nxt]=1;
        }
    }
    string ans="";
    int nr=0;
    while(nr!=start)
    {
        ans.push_back(cif[nr]+'0');
        nr=pref[nr];
    }
    ans.push_back('1');
    reverse(ans.begin(),ans.end());
    out<<ans;
    return 0;
}