Cod sursa(job #679098)

Utilizator rootsroots1 roots Data 12 februarie 2012 19:21:22
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>
#include <cstring>

#define maxN 2000001

using namespace std;

ifstream in;
ofstream out;

struct queue
{
    int rest,cif,nod;
}q[maxN];

int r[maxN];

inline int eucl(int a,int b)
{
    if(b==0) return a;
    for(int r=a%b;b;r=a%b,a=b,b=r);

    return a;
}

inline void print(int nod)
{
    if(q[nod].nod==0)
    {
        out<<'1';
        return;
    }

    print(q[nod].nod);
    out<<q[nod].cif;
}

int main()
{
    int A,B,mod;

    in.open("multiplu.in");

    in>>A>>B;

    in.close();

    mod=eucl(A,B);
    mod=((long long)A*B)/mod;

    out.open("multiplu.out");

    memset(r,0,sizeof(r));
    q[1].rest=1;
    q[1].cif=1;
    q[1].nod=0;
    int head,tail;
    head=tail=1;

    while(head<=tail)
    {
        int rest=q[head].rest;

        rest*=10;
        rest%=mod;

        if(r[rest]==0)
        {
            r[rest]=1;
            q[++tail].rest=rest;
            q[tail].cif=0;
            q[tail].nod=head;
        }

        if(rest==0)
        {
            print(tail);
            break;
        }

        ++rest;
        rest%=mod;

        if(r[rest]==0)
        {
            r[rest]=1;
            q[++tail].rest=rest;
            q[tail].cif=1;
            q[tail].nod=head;
        }

        if(rest==0)
        {
            print(tail);
            break;
        }

        head++;
    }

    out<<'\n';

    out.close();

    return 0;
}