Cod sursa(job #1022427)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 5 noiembrie 2013 13:30:51
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>

#define maxn 2000000

using namespace std;

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

int a,b,q[maxn],from[maxn],target,s,l;
bool viz[maxn],wh[maxn];

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

void recon (int x)
{
    if (x==1)
    {
        fout<<1;
        return;
    }

    recon (from[x]);

    fout<<wh[x];
}

int main()
{
    fin>>a>>b;

    target = a*b/cmmdc(a,b);

    q[1] = 1;
    viz[1] = 1;
    from[1] = -1;
    l=1;

    for (s=1; s<=l; ++s)
    {
        int x = (q[s]*10)%target;

        if (!viz[x])
        {
            viz[x] = 1;
            from[x] = q[s];
            q[++l] = x;
        }

        if (x==0)
            break;

        x = (q[s]*10+1)%target;

        if (!viz[x])
        {
            viz[x] = 1;
            from[x] = q[s];
            wh[x] = 1;
            q[++l] = x;
        }

        if (x==0) break;
    }

    recon (0);
}