Pagini recente » Cod sursa (job #479959) | Cod sursa (job #2267616) | Cod sursa (job #1077827) | Cod sursa (job #1385231) | Cod sursa (job #2964653)
#include <fstream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
ifstream in ("multiplu.in");
ofstream out ("multiplu.out");
const int max_size = 2e6 + 1;
int viz[max_size], t[max_size], sol[max_size], x, ans;
queue <int> q;
vector <int> rez;
void bfs ()
{
q.push(1);
viz[1] = 1;
sol[1] = 1;
while (!q.empty())
{
int nod = q.front();
q.pop();
for (int i = 0; i < 2; i++)
{
int nou = (nod * 10 + i) % x;
if (viz[nou] == 0)
{
viz[nou] = 1;
sol[nou] = i;
t[nou] = nod;
if (nou == 0)
{
ans = nou;
break;
}
q.push(nou);
}
}
}
}
int main ()
{
int a, b;
in >> a >> b;
x = a * b / __gcd(a, b);
bfs();
int ind = 0;
while (ind != 1)
{
rez.push_back(sol[ind]);
ind = t[ind];
}
reverse(rez.begin(), rez.end());
out << 1;
for (auto f : rez)
{
out << f;
}
in.close();
out.close();
return 0;
}