Pagini recente » Cod sursa (job #1758401) | Cod sursa (job #1963159) | Cod sursa (job #3197812) | Cod sursa (job #1155637) | Cod sursa (job #2786266)
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2e6 + 5;
bool viz[N];
int ant[N];
char val[N];
void bfs(int mod) {
queue<int> q;
q.push(1);
viz[1] = true;
val[1] = '1';
ant[1] = -1;
while (!q.empty()) {
auto rest = q.front();
q.pop();
int cu0 = rest * 10 % mod;
int cu1 = (rest * 10 + 1) % mod;
if (!viz[cu0]) {
viz[cu0] = true;
ant[cu0] = rest;
val[cu0] = '0';
if (!cu0)
return;
q.push(cu0);
}
if (!viz[cu1]) {
viz[cu1] = true;
ant[cu1] = rest;
val[cu1] = '1';
if (!cu1)
return;
q.push(cu1);
}
}
}
int main() {
ifstream cin("multiplu.in");
ofstream cout("multiplu.out");
int a, b, x;
cin >> a >> b;
cin.close();
x = a * b / __gcd(a, b);
bfs(x);
int nod = 0;
string s;
s.reserve(100);
while (nod != -1) {
s.push_back(val[nod]);
nod = ant[nod];
}
reverse(s.begin(), s.end());
cout << s;
cout.close();
return 0;
}