Cod sursa(job #2509841)

Utilizator stefanpiturStefan Alexandru Pitur stefanpitur Data 14 decembrie 2019 23:28:19
Problema Multiplu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <iostream>
#include <cstdio>
using namespace std;
const int SIZE_MAX = 2000000;
int ult[SIZE_MAX],pred[SIZE_MAX];
int q[SIZE_MAX];

int cmmdc(int a, int b){
    int r;
    while(a%b){
        r = a%b;
        a = b;
        b = r;
    }
    return b;
}

int main()
{
    FILE *fin, *fout;
    int a,b,m,st,dr,nr,next;
    bool solved;
    fin = fopen("multiplu.in","r");
    fout = fopen("multiplu.out","w");
    fscanf(fin,"%d %d",&a,&b);
    m = a*b/cmmdc(a,b);
    st = 0, dr = -1;
    for(int i=0; i<m; i++)
        ult[i] = -1;
    q[++dr] = 1, ult[1] = 1, pred[1] = 0;
    solved = false;
    while(!solved){
        nr = q[st++];
        if(nr == 0){
            solved = true;
            continue;
        }
        next = nr*10%m;
        if(ult[next] == -1){
            ult[next] = 0;
            pred[next] = nr;
            q[++dr] = next;
        }
        next = (next+1)%m;
        if(ult[next] == -1){
            ult[next] = 1;
            pred[next] = nr;
            q[++dr] = next;
        }
    }
    dr = -1;
    while(nr != 1){
        q[++dr] = ult[nr];
        nr = pred[nr];
    }
    q[++dr] = ult[nr];
    while(dr >= 0){
        fprintf(fout,"%d",q[dr]);
        dr--;
    }
    fclose(fin);
    fclose(fout);
    return 0;
}