Pagini recente » Cod sursa (job #2020767) | Cod sursa (job #71594) | Cod sursa (job #2147275) | Cod sursa (job #1652713) | Cod sursa (job #2840912)
#include <fstream>
#include <queue>
#include <vector>
#define NMAX 6000005
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
bool viz[NMAX];
int cif[NMAX], tata[NMAX];
const int val[2] = { 1,0 };
void reinit()
{
for (int i = 1; i <= NMAX; i++)
{
tata[i] = -1;
cif[i] = 0;
}
}
void cautNumar(int rest, int imp)
{
reinit();
queue<int> q;
q.push(1);
int sol = -1;
while (!q.empty())
{
int elem = q.front();
q.pop();
for (int i = 0; i < 2; i++)
{
int num = elem * 10 + val[i];
num %= imp;
if (!viz[num])
{
viz[num] = true;
q.push(num);
cif[num] = val[i];
tata[num] = elem;
if (num == rest)
{
sol = num;
break;
}
}
}
}
if (sol == -1)
{
//nu am solutie
fout << "-1\n";
return;
}
//parcurg vec de tati
vector<int>s;
s.push_back(cif[sol]);
while (tata[sol] > 0)
{
sol = tata[sol];
s.push_back(cif[sol]);
}
for (int i = s.size() - 1; i >= 0; i--)
{
fout << s[i];
}
fout << "\n";
}
int cmmdc(int a, int b)
{
int rest = a % b;
while (rest != 0)
{
a = b;
b = rest;
rest = a % b;
}
return b;
}
int main()
{
int a, b;
fin >> a >> b;
int cmdc = cmmdc(a, b);
int cmmmc = (a / cmdc) * (b / cmdc);
cautNumar(0, cmmmc);
return 0;
}