Cod sursa(job #2277676)

Utilizator mariusn01Marius Nicoli mariusn01 Data 6 noiembrie 2018 18:34:40
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>

using namespace std;

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

int t[2000001], c[2000001], U[2000001], v[2000001];
int p, u, ultimaCifra, a, b, m, nxt;
void drum(int u) {
    if (u!=0) {
        drum(t[u]);
        fout<<U[u];
    }
}

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

int main () {


    fin>>a>>b;
    m = a/cmmdc(a, b)*b;

    c[1] = 1;
    p = 1;
    u = 1;
    v[1] = 1;
    U[1] = 1;
    while (p <= u) {
        for (ultimaCifra = 0; ultimaCifra <= 1; ultimaCifra++) {
            nxt = (c[p] * 10 + ultimaCifra) % m;
            if (v[nxt] == 0) {
                u++;
                c[u] = nxt;
                v[nxt] = 1;
                U[u] = ultimaCifra;
                t[u] = p;
                if (nxt == 0) {
                    /// gasiram restul 0
                    p = u+1;
                    break;
                }
            }
        }
        p++;
    }
    drum(u);
    return 0;
}