Cod sursa(job #2330792)

Utilizator anamariatoaderAna Toader anamariatoader Data 28 ianuarie 2019 20:40:15
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>

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

int a,b,x,y,p,u,c,s[100],tata[2000005],k;
bool f[2000001];
struct numar{
    int x,b;
}q[2000005];

void show(int x){
    s[++k]=x;
    int poz=p;
    while(poz>0){
        s[++k]=q[poz].b;
        poz=tata[poz];
    }
    for(int i=k;i>0;i--)
        fout<<s[i];
}

int cmmmc(int a, int b){
    int x=a,y=b,r;
    while(y!=0){
        r=x%y;
        x=y;
        y=r;
    }
    return a*b/x;
}

int main()
{
    fin>>a>>b;
    x=cmmmc(a,b);
    q[1].x=q[1].b=1;
    p=u=1;
    while(1){
        c=(q[p].x*10)%x;
        if(c==0){
            show(0);
            return 0;
        }
        if(f[c]==0){
            q[++u].x=c;
            q[u].b=0;
            f[c]=1;
            tata[u]=p;
        }
        c=(q[p].x*10+1)%x;
        if(c==0){
            show(1);
            return 0;
        }
        if(f[c]==0){
            q[++u].x=c;
            q[u].b=1;
            f[c]=1;
            tata[u]=p;
        }
        p++;
    }
    return 0;
}