Cod sursa(job #1802738)

Utilizator raluca1234Tudor Raluca raluca1234 Data 10 noiembrie 2016 17:00:47
Problema Multiplu Scor 100
Compilator cpp Status done
Runda laborator_10i Marime 1.15 kb
#include <cstdio>
#define lim 2000000
#define NUL -1
int st[lim],prev[lim];
char fr[lim],val[lim];

int cmmdc(int a,int b){
    int r;
    while(b!=0){
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int main(){
    freopen("multiplu.in", "r", stdin);
    freopen("multiplu.out", "w", stdout);
    int a,b,m,bg,ed,pp,nxt;
    scanf("%d%d",&a,&b);
    m=a*b/cmmdc(a,b);
    bg=1;
    ed=1;
    st[1]=1;
    fr[1]=1;
    prev[1]=NUL;
    pp=0;
    while(pp==0){
        nxt=(st[bg]*10+0)%m;
        if(fr[nxt]==0){
            ed++;
            prev[ed]=bg;
            st[ed]=nxt;
            val[ed]=0;
            fr[nxt]=1;
        }
        if(nxt==0)
            pp=ed;
        nxt=(st[bg]*10+1)%m;
        if(fr[nxt]==0){
            ed++;
            prev[ed]=bg;
            st[ed]=nxt;
            val[ed]=1;
            fr[nxt]=1;
        }
        if(nxt==0)
            pp=ed;
        bg++;
    }
    ed=0;
    while(prev[pp]!=NUL){
        ed++;
        fr[ed]=val[pp];
        pp=prev[pp];
    }
    ed++;
    fr[ed]=1;
    for(bg=ed;bg>=1;bg--)
        printf("%d", fr[bg]);
    return 0;
}