Cod sursa(job #602334)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 10 iulie 2011 20:48:11
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <iostream>
#include <fstream>

#define Max 2000005

using namespace std;

ofstream fout ("multiplu.out");
int M, Queue[Max], Father[Max], Digit[Max];
bool V[Max];

int CMMDC (int a, int b)
{
    int r;
    while (b!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}

void Read ()
{
    ifstream fin ("multiplu.in");
    int a, b;
    fin >> a >> b;
    M=a*b/CMMDC (a, b);
    fin.close ();
}

void Print (int P)
{
    if (P!=0)
    {
        Print (Father[P]);
        fout<<Digit[P];
    }
}

int main()
{
    Read ();
    Queue[0]=Queue[1]=1;
    Digit[1]=1;
    for (int i=1; i<=Queue[0]; ++i)
    {
        int Mod0=(10*Queue[i])%M;
        int Mod1=(10*Queue[i]+1)%M;
        if (!V[Mod0])
        {
            Queue[++Queue[0]]=Mod0;
            Father[Queue[0]]=i;
            Digit[Queue[0]]=0;
            V[Mod0]=true;
            if (Mod0==0)
            {
                break;
            }
        }
        if (!V[Mod1])
        {
            Queue[++Queue[0]]=Mod1;
            Father[Queue[0]]=i;
            Digit[Queue[0]]=1;
            V[Mod1]=true;
            if (Mod1==0)
            {
                break;
            }
        }
    }
    Print (Queue[0]);
    return 0;
}