Cod sursa(job #1775698)

Utilizator mucenic_b101Bogdan Mucenic mucenic_b101 Data 10 octombrie 2016 17:07:04
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <string>
#include <queue>
#define MAXNR 2000000
using namespace std;

long long cmmdc(long long x, long long y) {
    while (y) {
        long long r = x % y;
        x = y;
        y = r;
    }

    return x;
}

int pre[MAXNR + 1];
bool digit[MAXNR + 1];
queue <int> Q;
string sol;

int main () {
    ifstream cin("multiplu.in");
    ofstream cout("multiplu.out");

    int a, b;
    cin >> a >> b;

    int c = (a * b) / cmmdc(a, b);

    if (c == 1) {
        cout << "1\n";
        return 0;
    }

    pre[1] = digit[1] = 1;
    Q.push(1);

    while (!pre[0]) {
        int x = Q.front();
        Q.pop();

        int k = (x * 10) % c;
        if (!pre[k]) {
            pre[k] = x;
            Q.push(k);
        }

        k = (k + 1) % c;
        if (!pre[k]) {
            pre[k] = x;
            digit[k] = 1;
            Q.push(k);
        }
    }

    int x = 0;
    while (x != 1) {
        sol += (digit[x] == 1 ? '1' : '0');
        x = pre[x];
    }

    cout << "1";
    for (int i = sol.size() - 1 ; i >= 0 ; --i)
        cout << sol[i];
    cout << "\n";

    return 0;

}