Cod sursa(job #1962338)

Utilizator ana_dariaAna Daria Hendoreanu ana_daria Data 11 aprilie 2017 18:23:27
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>

using namespace std;
const int nmax=2000000;
struct Multiplu
{
    int c,r,t;
};
Multiplu q[nmax+5];
bool f[nmax+5],sol[nmax+5];
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++;
            f[r]=1;
            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++;
            f[r]=1;
            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;
}