Cod sursa(job #2000613)

Utilizator Gl0WCula Stefan Gl0W Data 14 iulie 2017 11:38:03
Problema Multiplu Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>

using namespace std;

ifstream fin ("multiplu.in");
ofstream fout("multiplu.out");
int a, b, r, mc, v[10005], w[10005], sol[10005], t[10005], last[10005], 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 ; last[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;
                last[u] = i;
                if(ve == 0){
                    p = u + 1;
                    break;
                }
            }

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