Cod sursa(job #1962316)

Utilizator ana_dariaAna Daria Hendoreanu ana_daria Data 11 aprilie 2017 18:15:01
Problema Multiplu Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>

using namespace std;
const int nmax=2000000;
struct Multiplu
{
    int c,r,t;
};
Multiplu q[nmax+2];
bool f[nmax+2],sol[nmax+2];
ifstream in("multiplu.in");
ofstream out("multiplu.out");
int main()
{
    int p,u,a,b,m,a1,b1,r,i=1,x;
    in>>a>>b;
    a1=a; b1=b;
    while(b1>0)
    {
        r=a1%b1;
        a1=b1;
        b1=r;
    }
    m=a/a1*b;
    p=u=1;
    q[p].c=1;
    q[p].r=1;
    q[p].t=0;
    while(p<=u)
    {
        r=q[p].r*10%m;
        if(f[r]==0)
        {
            u++;
            q[u].r=r;
            q[u].c=0;
            q[u].t=p;
            if(r==0)
                break;
        }
        r=(q[p].r*10+1)%m;
        if(f[r]==0)
        {
            u++;
            q[u].r=r;
            q[u].c=1;
            q[u].t=p;
            if(r==0)
                break;
        }
        p++;
    }
    x=u;
    while(x>0)
    {
        sol[i]=q[x].c;
        //out<<sol[i];
        x=q[x].t;
        i++;
    }
    x=i-1;
    for(i=x;i>=1;i--)
        out<<sol[i];
    return 0;
}