Pagini recente » Cod sursa (job #1937865) | Cod sursa (job #2456432) | Cod sursa (job #126052) | Cod sursa (job #1986557) | Cod sursa (job #3329387)
#include <bits/stdc++.h>
using namespace std;
/**
C = 7
1 2 3 4 5 6 7 8 9 10
q = 1, 10, 11, 100, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101
q = 1, 3 4 2 5 6 0
u = 1 0 1 0 0 1 0
pred= 0 1 1 2 3 3 4
nr = 0001
1111111 - 1111 = 1110000
a % p = r
b % p = r
a-b diviz cu p
a = p*c1 + r
b = p*c2 + r
*/
ifstream fin("a.in");
ofstream fout("a.out");
int c[4];
bitset<2000001> fr;
int q[2000001], pr, ul;
bitset<2000001> u; /// ultima cifra
int pred[2000001];
void Afis(int k)
{
string sol = "";
while (k != 0)
{
if (u[k] == 0) sol = "0" + sol;
else sol = "1" + sol;
k = pred[k];
}
fout << sol << "\n";
}
int main()
{
int a, b, c, k, poz;
fin >> a >> b;
if (a == 1 && b == 1)
{
fout << "1\n";
return 0;
}
c = a * b / __gcd(a, b);
/// cel mai mic numar cu cifre 0 si 1 care se imparte la c
k = pr = ul = 1;
q[1] = 1;
fr[1] = 1;
u[k] = 1;
pred[k] = 0;
while (1)
{
poz = pr;
a = q[pr++];
b = a * 10 % c;
if (fr[b] == 0)
{
fr[b] = 1;
q[++ul] = b;
k++;
u[k] = 0;
pred[k] = poz;
}
if (b == 0)
{
Afis(k);
return 0;
}
b = (a * 10 + 1) % c;
if (fr[b] == 0)
{
fr[b] = 1;
q[++ul] = b;
k++;
u[k] = 1;
pred[k] = poz;
}
if (b == 0)
{
Afis(k);
return 0;
}
}
return 0;
}