Cod sursa(job #2497718)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 23 noiembrie 2019 10:37:12
Problema Multiplu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <bits/stdc++.h>
#include <queue>
#include <vector>

#define LIM 2000005
using namespace std;

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

typedef unsigned long long ull;
ull a, b;
int fr[LIM], last[LIM];
bool cif[LIM];
queue<int> q;
vector<int> v;

int main()
{
    fin >> a >> b;

    last[1] = -1;
    cif[1] = 1;
    int cmmmc = (a * b) / __gcd(a, b);
    q.push(1);
    while(fr[0] == 0){
        int p = q.front();
        q.pop();

        if(fr[(p * 10) % cmmmc] == 0)
        {
            q.push((p * 10) % cmmmc);
            fr[(p * 10) % cmmmc] = 1;
            last[(p * 10) % cmmmc] = p;
            cif[(p * 10) % cmmmc] = 0;
        }
        if(fr[(p * 10 + 1) % cmmmc] == 0){
            q.push((p * 10 + 1) % cmmmc);
            fr[(p * 10 + 1) % cmmmc] = 1;
            last[(p * 10 + 1) % cmmmc] = p;
            cif[(p * 10 + 1) % cmmmc] = 1;
        }
    }

    int where = 0;
    while(where != -1){
        v.push_back(cif[where]);
        where = last[where];
    }

    for(int i = v.size() - 1; i >= 0; --i)
        fout << v[i];
    fout << '\n';
    return 0;
}