Cod sursa(job #1962356)

Utilizator mirelPmirel p mirelP Data 11 aprilie 2017 18:30:50
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>

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

const int NMAX=2000000;
struct MULTIPLU
{
    int c,r,t;
};
MULTIPLU q[NMAX+5];
bool f[NMAX+5],sol[NMAX+5];

int main()
{
    int A,B,M,CA,CB,r,i=1,p,u,a;
    bool ok=0;
    fin>>A>>B;
    CA=A;
    CB=B;
    while(B>0)
    {
        r=A%B;
        A=B;
        B=r;
    }
    M=CA/A*CB;
    p=1;
    u=1;
    q[p].c=1;
    q[p].r=1;
    q[p].t=0;
    f[q[p].r]=1;
    while(p<=u)
    {
        r=(q[p].r*10+0)%M;
        if(f[r]==0)
        {
            f[r]=1;
            u++;
            q[u].c=0;
            q[u].r=r;
            q[u].t=p;
            if(r==0)
                break;
        }
        r=(q[p].r*10+1)%M;
        if(f[r]==0)
        {
            f[r]=1;
            u++;
            q[u].c=1;
            q[u].r=r;
            q[u].t=p;
            if(r==0)
                break;
        }
        p++;
    }


    while(q[u].t!=0)
    {
        sol[i]=q[u].c;
        u=q[u].t;
        i++;
    }
    sol[i]=q[u].c;
    for(a=i;a>0;a--)
        fout<<sol[a];

        fin.close();
        fout.close();
    return 0;
}