Cod sursa(job #1797821)

Utilizator maria15Maria Dinca maria15 Data 4 noiembrie 2016 19:25:34
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>

using namespace std;

int c[2000010], vizitat[2000010], cifra[2000010], t[2000010];

int p, u, a, b, m, r, sol;

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

void solutie (int u) {
    if (u!=0) {
        solutie(t[u]);
        fout<<cifra[u];
    }
}

int main () {
    fin>>a>>b;
    m=a*b;
    while(b!=0){
        r=a%b;
        a=b;
        b=r;
    }
    m/=a;
    c[1]=1%m;
    vizitat[1] = 1;
    cifra[1] = 1;
    p=u=1;
    while(p<=u){
        for(int j=0;j<=1;j++){
            int rnext = (c[p] * 10 + j)%m;
            if (vizitat[rnext] == 0) {
                u++;
                c[u] = rnext;
                vizitat[rnext] = 1;
                cifra[u] = j;
                t[u] = p;
                if (rnext == 0) {
                    solutie(u);
                    return 0;
                }
            }
        }
        p++;
    }
    return 0;
}