Pagini recente » Cod sursa (job #582560) | Cod sursa (job #189679) | Cod sursa (job #364406) | Cod sursa (job #1780742) | Cod sursa (job #2783637)
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
ifstream f ("multiplu.in");
ofstream g ("multiplu.out");
int cmmdc (int a , int b){
int r;
while (b){
r = a % b;
a = b;
b = r;
}
return a;
}
vector <int> sol;
int const N = 3e6 + 1;
int edge [N] , t [N] , viz [N];
void out (int nr){
int nod = nr;
while (nod != -1){
sol.push_back (edge [nod]);
nod = t [nod];
}
reverse (sol.begin () , sol.end ());
for(auto y : sol)
g << y;
}
int main()
{
int a , b;
f >> a >> b;
int x = a * b / cmmdc (a , b);
viz [1] = 1;
queue <int> q;
q.push (1);
t [1] = -1;
edge [1] = 1;
while (true){
int nr = q.front ();
q.pop ();
int r1 = (nr * 10) % x;
int r2 = (nr * 10 + 1) % x;
if (! r1){
sol.push_back (0);
out (nr);
exit (0);
}
if (! r2){
sol.push_back (1);
out (nr);
exit (0);
}
if (! viz [r1]){
q.push (r1);
viz [r1] = 1;
t [r1] = nr;
edge [r1] = 0;
}
if (! viz [r2]){
q.push (r2);
viz [r2] = 1;
t [r2] = nr;
edge [r2] = 1;
}
}
return 0;
}