Cod sursa(job #631642)

Utilizator zloteanu.adrianzloteanu adrian nichita zloteanu.adrian Data 9 noiembrie 2011 11:28:59
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include<fstream>
using namespace std;
long pred[2000001],ad[2000001];
long lung,coada[2000001];
int main()
{
    ifstream q("multiplu.in");
    ofstream w("multiplu.out");
    long A,B,c,M;
    q>>A>>B;
    M=A*B;
    while (B)
    {
        c=A%B;
        A=B;
        B=c;
    }
    M/=A;
    lung=1;
    coada[1]=1;
    pred[1]=0;
    ad[1]=1;
    long nrnou;
    for(long i=1;i<=lung;i++)
    {
        nrnou=(coada[i]*10)%M;
        if(pred[nrnou]==0)//nod nou
        {
            lung++;
            coada[lung]=nrnou;
            pred[nrnou]=coada[i];
            ad[nrnou]=0;
        }
        if(nrnou==0)
        {
            printf("Done");
            return 0;
        }
        nrnou=(coada[i]*10+1)%M;
        if(pred[nrnou]==0)//nod nou
        {
            lung++;
            coada[lung]=nrnou;
            pred[nrnou]=coada[i];
            ad[nrnou]=1;
        }
        if(nrnou==0)
        {
            while(i!=1){
                i=ad[coada[i]];
                w<<ad[i];
                i=pred[i];
            }
            return 0;
        }
    }

return 0;
}