Cod sursa(job #1796300)

Utilizator osiaccrCristian Osiac osiaccr Data 3 noiembrie 2016 12:09:02
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>
#define DIM 2000010

using namespace std;

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

int a,b,m,aa,bb,p,u,v[DIM],L[DIM],i,rnext,t[DIM],c[DIM],r,s[DIM],k;

int main()
{
    fin>>a>>b;
    aa = a;
    bb = b;

    while (bb != 0) {
        r = aa%bb;
        aa = bb;
        bb = r;
    }

    m=a/aa*b;
    //fout<<aa*bb/b;

    //coda
    p=1;u=1;
    c[1]=1;v[1]=1;L[1]=1;
    while(p<=u)
    {
        for(i=0;i<=1;i++)
        {
            rnext = (c[p]*10 + i)%m;
            if(v[rnext] == 0)
            {
                u++;
                c[u]=rnext;
                v[rnext]=1;
                L[u]=i;
                t[u]=p;
                if(rnext == 0)
                {
                    while (u != 0) {
                        s[++k] = L[u];
                        u = t[u];
                    }
                    for (i=k;i>=1;i--)
                        fout<<s[i]<<" ";
                    //solutie
                    return 0;
                }
            }
        }
        p++;
    }

    return 0;
}