Cod sursa(job #347201)

Utilizator freak93Adrian Budau freak93 Data 11 septembrie 2009 13:52:48
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<fstream>
#include<bitset>

using namespace std;

const char iname[]="multiplu.in";
const char oname[]="multiplu.out";
const int maxv=2000007;

ifstream f(iname);
ofstream g(oname);

int cmmdc(int a,int b)
{
    if(b==0)
        return a;
    return cmmdc(b,a%b);
}

bitset<maxv> rest;

int coada[maxv],n,i,j,a,b,lp[maxv],cif[maxv],k;

void afis(int x)
{
    if(x==0)
        return;
    afis(lp[x]);
    g<<cif[x];
}

int main()
{
    f>>a>>b;
    n=cmmdc(a,b);
    n=(a*b)/n;

    if(n==1)
    {
        g<<1<<"\n";
        f.close();
        g.close();

        return 0;
    }

    coada[++i]=1;
    rest[1]=1;
    cif[1]=1;

    for(j=1;j<=i;++j)
    {
        k=coada[j];
        if(rest[(k*10)%n]==0)
            rest[(k*10)%n]=1,coada[++i]=(k*10)%n,cif[i]=0,lp[i]=j;
        if(rest[0]==1)
            break;
        if(rest[(k*10+1)%n]==0)
            rest[(k*10+1)%n]=1,coada[++i]=(k*10+1)%n,cif[i]=1,lp[i]=j;
        if(rest[0]==1)
            break;
    }

    afis(i);
    g<<"\n";

    f.close();
    g.close();

    return 0;
}