Cod sursa(job #2497757)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 23 noiembrie 2019 10:55:54
Problema Multiplu Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 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 last[LIM], vec[LIM];
bool fr[LIM], cif[LIM];
int stP = 1, lsP = 1;
vector<int> v;

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

    int poz = 1;
    vec[1] = 1;
    last[1] = -1;
    cif[1] = 1;
    int pz = 0;
    int cmmmc = (a * b) / __gcd(a, b);
    while(1){
        int p = vec[stP];
        if(fr[(p * 10) % cmmmc] == 0)
        {
            vec[++lsP] = ((p * 10) % cmmmc);
            fr[lsP] = 1;
            last[lsP] = stP;
            cif[lsP] = 0;
            if((p * 10) % cmmmc == 0){
                pz = lsP;
                break;
            }
        }
        if(fr[(p * 10 + 1) % cmmmc] == 0){
            vec[++lsP] = ((p * 10 + 1) % cmmmc);
            fr[lsP] = 1;
            last[lsP] = stP;
            cif[lsP] = 1;
            if((p * 10 + 1) % cmmmc == 0){
                pz = lsP;
                break;
            }
        }
        ++stP;
    }

    int where = pz;
    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;
}