Cod sursa(job #1327464)

Utilizator andreeadeacAndreea Ioana Deac andreeadeac Data 26 ianuarie 2015 19:10:24
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
using namespace std;

ifstream in("multiplu.in");
ofstream out("multiplu.out");
const int N=2000000;
int c[N+1],pred[N+1],ult[N+1],a,b;

int cmmmc(int a, int b){
    int x=a,y=b;
    while (a!=b){
        if(a<b)
            a=a+x;
        else
            b=b+y;
    }
    return a;
}

void multiplu(int x){
    int p=1,u=1,nr1,nr2,rest,cod=1;
    c[p]=1;
    pred[1]=-1;
    ult[1]=1;
    while(cod==1){
        nr1=c[p]*10;
        rest=nr1%x;
        if(pred[rest]==0){
            u++;
            c[u]=rest;
            ult[rest]=0;
            pred[rest]=c[p];
        }
        if(rest==0)
            cod=0;
        //out<<nr1<<" "<<rest<<" "<<ult[rest]<<" "<<pred[rest]<<"  ... ";

        nr2=c[p]*10+1;
        rest=nr2%x;
        if(pred[rest]==0){
            u++;
            c[u]=rest;
            ult[rest]=1;
            pred[rest]=c[p];
        }
        if(rest==0)
            cod=0;
        //out<<nr2<<" "<<rest<<" "<<ult[rest]<<" "<<pred[rest]<<"\n";

        p++;
    }
}

void numar(int x){
    if(pred[x]!=-1)
        numar(pred[x]);
    out<<ult[x];
}
int main()
{
    in>>a>>b;
    int x=cmmmc(a,b);
    multiplu(x);
    numar(0);
    return 0;
}