Cod sursa(job #2400482)

Utilizator BogauuuBogdan Ivancu Bogauuu Data 8 aprilie 2019 20:06:39
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>

using namespace std;

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

bool v[2000005];
int af[2000005],t[2000005],c[2000005],aff[2000005];

void afisare(int i)
{
    int k=0;
    while (t[i]!=0)
    {
        k++;
        aff[k]=af[i];
        i=t[i];
    }
    k++;
    aff[k]=af[i];
    for (int i=k;i>=1;i--) fout << aff[i];
}

int a,b,p,r,m,st,dr,u,n;

int main()
{
    fin >> a >> b;
    p=a*b;
    while (b!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    m=p/a;
    v[1]=1;
    st=1;
    dr=1;
    c[1]=1;
    af[1]=1;
    while (st<=dr)
    {
        for (u=0;u<=1;u++)
        {
            n=c[st]*10+u;
            n%=m;
            if (v[n]==0)
            {
                v[n]=1;
                dr++;
                c[dr]=n;
                t[dr]=st;
                af[dr]=u;
            }
            if (n==0)
            {
                afisare(dr);
                st=dr;
                break;
            }
        }
        st++;
    }

    return 0;
}