Cod sursa(job #2135627)

Utilizator Bogdan_BuzatuBuzatu Bogdan Mihai Bogdan_Buzatu Data 18 februarie 2018 23:21:25
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>

using namespace std;

ifstream fin ("multiplu.in");
ofstream fout("multiplu.out");
int a, b, r, mc, v[1000001], w[1000001], sol[1000001], t[1000001], ultimul[1000001], k, p, u, i, ve, aa, bb;
int main()
{
    fin>>a>>b;
    aa = a; bb = b;
    r = a % b;
    while(r){
        a = b;
        b = r;
        r = a % b;
    }
    mc = aa * bb / b;
    v[1] = 1;
    w[1] = 1;
    t[1] = 0;
    ultimul[1] = 1;
    p = 1;
    u = 1;
    while(p <= u){
        for(i = 0; i <= 1; i++){
            ve = (v[p]*10 + i) % mc;
            if(w[ve] == 0){
                u++;
                v[u] = ve;
                w[ve] = 1;
                t[u] = p;
                ultimul[u] = i;
                if(ve == 0){
                    p = u + 1;
                    break;
                }
            }

        }
        p++;
    }
    while(u != 0){
        k++;
        sol[k] = ultimul[u];
        u=t[u];
    }
    for(i = k; i >= 1; i--){
        fout<<sol[i];
    }
    return 0;
}