Cod sursa(job #3140233)

Utilizator traiandobrinDobrin Traian traiandobrin Data 4 iulie 2023 20:48:10
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
ifstream in("multiplu.in");
ofstream out("multiplu.out");
struct rems
{
    long long m,digit;
};
int f[(int)(2e6+6)],lst[(int)(2e6+6)],vis[2000005];
int main()
{
    long long a,b;
    in>>a>>b;
    long long gcd=__gcd(a,b);
    long long lcm=a*b/gcd;
    queue<rems> q;
    q.push({1,-1});
    lst[0]=lst[1]=-1;
    while(!q.empty())
    {
        rems nr=q.front();
        q.pop();
       // if(vis[nr.m])continue;
        vis[nr.m]=1;
        int add0=nr.m*10;
        int add1=nr.m*10+1;
        add1%=lcm;
        add0%=lcm;
        if(!vis[add0])
        {
            q.push({add0,0});
            lst[add0]=0;
            f[add0]=nr.m;
            vis[add0]=1;
        }
        if(!vis[add1])
        {
            q.push({add1,1});
            lst[add1]=1;
            f[add1]=nr.m;
            vis[add1]=1;
        }
        if(add0==0||add1==0)
            break;
    }
    int curr=0;
    string s;

    while(lst[curr]!=-1)
    {
        s+=48+lst[curr];
        curr=f[curr];
    }
    reverse(s.begin(),s.end());
    out<<"1"<<s;
    return 0;
}