Pagini recente » Borderou de evaluare (job #2010082) | Cod sursa (job #2818240) | Cod sursa (job #2939322) | Cod sursa (job #905435) | Cod sursa (job #3278383)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
const int M = 2e6;
int cmmmc(int a, int b){
int n = a, m = b;
while (m != n){
if (n < m){
n += a;
}
else if(n > m){
m += b;
}
}
return n;
}
void refac_numarul(int x, vector<pair<int, int>> &pred, ofstream &out){
if (x == 1){
out << 1;
return;
}
refac_numarul(pred[x].first, pred, out);
out << pred[x].second;
}
int main()
{
ifstream in("multiplu.in");
ofstream out("multiplu.out");
int a, b;
in >> a >> b;
int m = cmmmc(a, b);
vector<bool> viz(m, false);
pair <int, int> init = {-1, -1};
vector<pair<int,int>> pred(m, init);
queue<int> q;
q.push(1);
pred[1].first = 0;
pred[1].second = -1;
while (!q.empty()){
int x = q.front();
q.pop();
int y = x * 10 % m;
if (pred[y].first == -1){
q.push(y);
pred[y].first = x;
pred[y].second = 0;
}
y = (x*10 + 1) % m;
if (pred[y].first == -1){
q.push(y);
pred[y].first = x;
pred[y].second = 1;
}
}
refac_numarul(0, pred, out);
in.close();
out.close();
return 0;
}