Cod sursa(job #3140229)

Utilizator traiandobrinDobrin Traian traiandobrin Data 4 iulie 2023 20:41:54
Problema Multiplu Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
ifstream in("multiplu.in");
ofstream out("multiplu.out");
struct rems
{
    int m,digit;
};
int f[(int)(2e6+6)],lst[(int)(2e6+6)],vis[2000005];
int main()
{
    int a,b;
    in>>a>>b;
    int gcd=__gcd(a,b);
    int 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;}
        if(!vis[add1]){
        q.push({add1,1});
        lst[add1]=1;
        f[add1]=nr.m;}
        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;
}