Pagini recente » Cod sursa (job #1103104) | Cod sursa (job #2843711) | Cod sursa (job #2578328) | Cod sursa (job #1769782) | Cod sursa (job #3166528)
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int cmmdc(int d, int i) {
int r;
do {
r = d % i;
d = i;
i = r;
} while (r != 0);
return d;
}
int cmmmmc(int a, int b) { return (a * b) / cmmdc(a, b); }
int main() {
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
int A, B;
fin >> A >> B;
int M = cmmmmc(A, B); // Calculam cel mai mic multiplu comun pentru A si B
vector<bool> obtinut(M, false); // Vector pentru a verifica daca un rest a fost vizitat sau nu
vector<int> p(M); // restul precedent
vector<int> cifra(M); // cifra corespunzatoare unui anumit rest
queue<int> q;
q.push(1); // Introducem restul numarului 1 la impartirea cu M
obtinut[1] = true;
p[1] = -1; // Inaintea primului rest nu avem o alt rest.
cifra[1] = 1;
while (not q.empty()) {
int c = q.front(); // restul curent
q.pop();
if (c == 0) { // Daca restul este 0, am gasit numarul
vector<int> sol;
for (int i = 0; c != -1; c = p[c]) {
sol.push_back(cifra[c]);
}
for (int i = sol.size() - 1; i >= 0; --i) {
fout << sol[i];
}
fout << '\n';
break;
}
for (int i : {0, 1}) {
int urm = (c * 10 + i) % M; // Adaugam cifra 0 la sfarsitul
if (not obtinut[urm]) {
q.push(urm);
obtinut[urm] = true;
p[urm] = c;
cifra[urm] = i;
}
}
}
fin.close();
fout.close();
return 0;
}