Cod sursa(job #1461119)

Utilizator anamariaraduAna Maria Radu anamariaradu Data 14 iulie 2015 19:34:55
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <fstream>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
const int NMAX=2000000;
bool f[NMAX];
struct queue
{
    bool c;
    int r,pred;
};
queue q[NMAX];
bool sol[NMAX];
int cmmdc(int a,int b)
{
    int r;
    while(b)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}

int main()
{
    int a,b,m,p,u,i,r0,r1;
    fin>>a>>b;
    m=a*b/cmmdc(a,b);
    p=u=1;
    q[u].c=1;
    q[u].r=1;
    q[u].pred=0;
    f[1]=1;
    if(a*b==1)
        fout<<1<<endl;
    else
    {
        while(p<=u)
        {
            r0=(q[p].r*10+0)%m;
            if(f[r0]==0)
                {
                    f[r0]=1;
                    u++;
                    q[u].c=0;
                    q[u].r=r0;
                    q[u].pred=p;
                    if(r0==0)
                        break;
                }
            r1=(q[p].r*10+1)%m;
            if(f[r1]==0)
                {
                    f[r1]=1;
                    u++;
                    q[u].c=1;
                    q[u].r=r1;
                    q[u].pred=p;
                    if(r1==0)
                        break;
                }
            p++;
        }
        int k=0;
        while(u>0)
        {
            sol[++k]=q[u].c;
            u=q[u].pred;
        }
        for(i=k;i>=1;i--)
            fout<<sol[i];
    }



    fin.close();
    fout.close();

    return 0;
}