Cod sursa(job #2323818)

Utilizator Carol_LucaCarol Luca Carol_Luca Data 19 ianuarie 2019 19:22:55
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <bits/stdc++.h>

#define pb push_back

#define ll long long



std::ifstream in("multiplu.in") ;

std::ofstream out("multiplu.out") ;



const int MAX = 2000005 ;



int a, b, lcm ;

int curr ;

std::vector <int> rez ;

int cif[MAX], ult[MAX] ;

bool avem[MAX] ;

std::queue < std::pair <int, int> > Q ;



inline int modCalc(int a, int b) {

    while (a >= b)

        a -= b ;

    return a ; }



int gcd(int a, int b) {

    if (b == 0)

        return a ;

    return gcd(b, modCalc(a, b)) ; }



signed main() {

    in >> a >> b ;

    if (a + b == 1) {

        out << 1 ;

        return 0 ; }

    lcm = a * b / gcd(a, b) ;

    Q.push({1, 0 }) ;

    avem[1] = 0 ;

    ult[curr] = -1 ;

    cif[curr] = 1 ;

    ll deacolo = -1 ;

    while (!Q.empty()) {

        std::pair <int, int> nod = Q.front() ;

        Q.pop() ;

        int r = nod.first, t = nod.second ;

        if (!avem[modCalc(r * 10, lcm)]) {

            curr++ ;

            Q.push({modCalc(r * 10, lcm), curr }) ;

            avem[modCalc(r * 10, lcm)] = 1 ;

            ult[curr] = t ;

            cif[curr] = 0 ;

            if (modCalc(r * 10, lcm) == 0) {

                deacolo = curr ;

                break ; } }

        if (!avem[modCalc(r * 10 + 1, lcm)]) {

            curr++ ;

            Q.push({modCalc(r * 10 + 1, lcm), curr }) ;

            avem[modCalc(r * 10 + 1, lcm)] = 1 ;

            ult[curr] = t ;

            cif[curr] = 1 ;

            if (modCalc(r * 10 + 1, lcm) == 0) {

                deacolo = curr ;

                break ; } } }

    while (deacolo != -1) {

        rez.pb(cif[deacolo]) ;

        deacolo = ult[deacolo] ; }

    std::reverse(rez.begin(), rez.end()) ;

    for (int x=0;x<rez.size();++x)

        out << rez[x] ;

    return 0 ;
}