Cod sursa(job #1416551)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 8 aprilie 2015 13:31:02
Problema Multiplu Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <stdio.h>
#define NIL -1
#define MAXN 2000000
int q[MAXN], r[MAXN], fr[MAXN], next[MAXN];
inline int cmmdc(int a, int b){
    int r;
    while(b){
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int main(){
    int a, b, k, st, dr, i, n;
    FILE *fin, *fout;
    fin=fopen("multiplu.in", "r");
    fout=fopen("multiplu.out", "w");
    fscanf(fin, "%d%d", &a, &b);
    k=a*b/cmmdc(a, b);
    if(k==1){
        fprintf(fout, "1\n");
    }else{
        q[0]=1;
        r[0]=1;
        fr[1]=1;
        next[0]=NIL;
        st=0;
        dr=1;
        while(fr[0]==0){
            if(fr[(10*r[st])%k]==0){
                q[dr]=0;
                r[dr]=(10*r[st])%k;
                fr[r[dr]]=1;
                next[dr]=st;
                dr++;
            }
            if(fr[(10*r[st]+1)%k]==0){
                q[dr]=1;
                r[dr]=(10*r[st]+1)%k;
                fr[r[dr]]=1;
                next[dr]=st;
                dr++;
            }
            st++;
        }
        dr--;
        while(r[dr]!=0){
            dr--;
        }
        r[0]=q[dr];
        n=1;
        dr=next[dr];
        while(dr!=NIL){
            r[n++]=q[dr];
            dr=next[dr];
        }
        for(i=n-1; i>=0; i--){
            fputc(r[i]+'0', fout);
        }
        fputc('\n', fout);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}