Cod sursa(job #3149535)

Utilizator amunnumeVlad Patrascu amunnume Data 9 septembrie 2023 17:43:11
Problema Multiplu Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <bits/stdc++.h>
#define N 2000005
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
int a,b,r,m,n,i,j,x,t[N],s[N+150];
bool f[N],c[N];
queue<int> q;
int main()
{
    fin>>a>>b;
    m=a*b;
    while(b)
    {
        r=a%b;
        a=b;
        b=r;
    }
    m/=a;
    if(m==1)
    {
        fout<<1;
        return 0;
    }
    f[1]=1;
    t[1]=-1;
    c[1]=1;
    q.push(1);
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        n=(x*10+1)%m;
        if(!f[n])
        {
            f[n]=1;
            t[n]=x;
            c[n]=1;
            q.push(n);
        }
        if(!n) break;
        n=(x*10+0)%m;
        if(!f[n])
        {
            f[n]=1;
            t[n]=x;
            c[n]=0;
            q.push(n);
        }
        if(!n) break;
    }
    x=0; j=0;
    while(j>=0)
    {
        s[++x]=c[j];
        j=t[j];
    }
    for(i=x;i>=1;--i)
    {
        fout<<s[i];
    }
    return 0;
}