Pagini recente » kmp_aib | Cod sursa (job #848851) | Cod sursa (job #2458656) | Cod sursa (job #294725) | Cod sursa (job #3225844)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
int q[2000003], pr, ul;
char c[2000003], pred[2000003];
bitset<2000003> fr;
string sol;
int main()
{
int a, b, x;
fin >> a >> b;
x = a / __gcd(a, b) *b;
pr = ul = 1;
q[pr] = 1;
c[pr] = '1';
fr[1] = 1;
while (fr[0] == 0)
{
a = q[pr];
pr++;
b = a * 10 % x;
if (fr[b] == 0)
{
fr[b] = 1;
q[++ul] = b;
c[ul] = '0';
pred[ul] = pr - 1;
}
if (b == 0) break;
b = (a * 10 + 1) % x;
if (fr[b] == 0)
{
fr[b] = 1;
q[++ul] = b;
c[ul] = '1';
pred[ul] = pr - 1;
}
}
while (ul != 0)
{
sol += c[ul];
ul = pred[ul];
}
reverse(sol.begin(), sol.end());
fout << sol;
return 0;
}