Cod sursa(job #1902637)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 4 martie 2017 18:25:28
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <bitset>

using namespace std;

struct NUMAR{
    int cifra, rest, tata;
};

vector <NUMAR> q;
bitset <2000005> viz_rest;
stack <int> rasp;
int m;

int cmmmc(int a, int b) {
    int r, a_Backup, b_Backup;

    a_Backup = a;
    b_Backup = b;

    while(b != 0) {
        r = a % b;
        a = b;
        b = r;
    }

    return a_Backup * b_Backup / a;
}

void urmatorul_numar(NUMAR a, int poz, int x) {
    a.cifra = x;
    a.rest = (a.rest * 10 + x) % m;
    a.tata = poz;
    if(viz_rest[a.rest] == 0) {
        viz_rest[a.rest] = 1;
        q.push_back(a);
    }
}

int main() {
    freopen("multiplu.in", "r", stdin);
	freopen("multiplu.out", "w", stdout);

    int a, b;
    scanf("%d%d", &a, &b);
    m = cmmmc(a, b);

    q.push_back({1, 1, -1});
    viz_rest[1] = 1;

    int i;
    for(i = 0; q[i].rest != 0; ++ i) {
        urmatorul_numar(q[i], i, 0);
        urmatorul_numar(q[i], i, 1);
    }

    while(q[i].tata != -1) {
        rasp.push(q[i].cifra);
        i = q[i].tata;
    }
    rasp.push(1);

    while(!rasp.empty()) {
        printf("%d", rasp.top());
        rasp.pop();
    }

    return 0;
}