Cod sursa(job #2560578)

Utilizator FastmateiMatei Mocanu Fastmatei Data 28 februarie 2020 09:37:27
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <bits/stdc++.h>
#define  NMAX 2000002

using namespace std;

ifstream fin("multiplu.in");
ofstream fout("multiplu.out");

int A,B;
int a[NMAX],cif[NMAX],pred[NMAX];
bool M[NMAX];

void Afisare(int ul)
{
    if(ul!=0)
    {
        Afisare(pred[ul]);
        fout<<cif[ul];
    }
}

int main()
{
    int j,i,x,pr=1,ul=1;
    fin>>A>>B;
    x=A/__gcd(A,B)*B;
    a[1]=1;
    cif[1]=1;
    pred[1]=0;
    M[1]=true;
    while(1)
    {
        i=a[pr];
        j=1LL*i*10%x;
        if(M[j]!=1)
        {
            M[j]=true;
            a[++ul]=j;
            cif[ul]=0;
            pred[ul]=pr;
            if(j==0)
            {
                Afisare(ul);
                return 0;
            }
        }
        j=(1LL*i*10+1)%x;
        if(M[j]!=1)
        {
            M[j]=true;
            a[++ul]=j;
            cif[ul]=1;
            pred[ul]=pr;
            if(j==0)
            {
                Afisare(ul);
                return 0;
            }
        }
        pr++;
    }
    return 0;
}