Pagini recente » Cod sursa (job #1123895) | Cod sursa (job #2420265) | Cod sursa (job #524761) | Cod sursa (job #1593700) | Cod sursa (job #1712735)
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
const int dim = 2000005;
int parent[dim], cif[dim];
bool vis[dim];
int main() {
int a, b;
fin >> a >> b;
if (a == b && a == 1) {
fout << 1;
return 0;
}
int m = a * b;
while (b) {
int r = a % b;
a = b;
b = r;
}
m /= a;
queue<int> que;
que.push(1);
vis[1] = 1;
cif[1] = 1;
parent[1] = -1;
for (; !que.empty(); que.pop()) {
int x = que.front();
if (x == 0)
break;
int aux = (x * 10) % m;
if (!vis[aux]) {
vis[aux] = 1;
que.push(aux);
parent[aux] = x;
cif[aux] = 0;
}
aux = (aux + 1) % m;
if (!vis[aux]) {
vis[aux] = 1;
que.push(aux);
parent[aux] = x;
cif[aux] = 1;
}
}
vector<int> sol;
for (int i = 0; i != -1; i = parent[i])
sol.push_back(cif[i]);
reverse(sol.begin(), sol.end());
for (int it : sol)
fout << it;
return 0;
}
//Trust me, I'm the Doctor!