Cod sursa(job #2312282)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 4 ianuarie 2019 16:40:39
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.73 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 (auto x : rez)
        out << x ;
    return 0 ; }