Cod sursa(job #2276185)

Utilizator TooHappyMarchitan Teodor TooHappy Data 4 noiembrie 2018 12:32:16
Problema Multiplu Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <bits/stdc++.h>
using namespace std;
 
ifstream in("multiplu.in");
ofstream out("multiplu.out");

const int Nmax = 2e6 + 10;

int gcd(int a, int b) {
    return (b ? gcd(b, a % b) : a);
}

int main() {
    ios::sync_with_stdio(false); in.tie(0); out.tie(0);

    int a, b; in >> a >> b;

    int m = (a * b) / gcd(a, b);

    queue< int > q; q.push(1);

    bool viz[Nmax];
    while(!q.empty()) {
        int x = q.front(); q.pop();

        if(!viz[(x * 10) % m]) {
            q.push(x * 10);
            if(x * 10 % m == 0) {
                out << x * 10 << "\n";
                break;
            }
        }
        if(!viz[(x * 10 + 1) % m]) {
            q.push(x * 10 + 1);
            if((x * 10 + 1) % m == 0) {
                out << x * 10 + 1 << "\n";
                break;
            }
        }
    }

    in.close(); out.close();

    return 0;
}