Pagini recente » Cod sursa (job #1038524) | Cod sursa (job #1493729) | Cod sursa (job #114059) | Cod sursa (job #2253725) | Cod sursa (job #2120223)
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin ("multiplu.in"); ofstream fout ("multiplu.out");
const int nmax = 2e6;
const int inf = 1 << 30;
int t[nmax + 1], c[nmax + 1];
bool viz[nmax + 1];
queue< int > q;
vector< int > v;
int gcd (int a, int b) {
while (b > 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
int main () {
int a, b;
fin >> a >> b;
int lcm = a * b / gcd(a, b);
q.push( 1 );
t[ 1 ] = 0;
viz[ 1 ] = 1;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int cif = 0; cif < 2; ++ cif) {
int y = (x * 10 + cif) % lcm;
if (viz[ y ] == 0) {
t[ y ] = x;
c[ y ] = cif;
viz[ y ] = 1;
q.push( y );
}
}
}
int r = 0;
while (r != 1) {
v.push_back(c[ r ]);
r = t[ r ];
}
v.push_back( 1 );
reverse(v.begin(), v.end());
for (auto i : v) {
fout.put(i + '0');
}
fin.close();
fout.close();
return 0;
}