Pagini recente » Cod sursa (job #3172211) | Cod sursa (job #2514986) | Cod sursa (job #1351313) | Cod sursa (job #3221987) | Cod sursa (job #2276243)
#include <bits/stdc++.h>
using namespace std;
ifstream in("multiplu.in");
ofstream out("multiplu.out");
const int Nmax = 2e6 + 10;
int gcd(int a, int b) {
return (b ? gcd(b, a % b) : a);
}
int tata[Nmax], cif[Nmax];
queue< int > q;
void getNumber(int x) {
if(x == -1) {
return;
}
getNumber(tata[x]);
out << cif[x];
}
int main() {
ios::sync_with_stdio(false); in.tie(0); out.tie(0);
int a, b; in >> a >> b;
int m = (a * b) / gcd(a, b);
if(m == 1) {
out << "1\n";
return 0;
}
q.push(1);
tata[1] = -1;
cif[1] = 1;
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = 0; i < 2; ++i) {
int nx = 10 * x + i;
int r = nx % m;
if(tata[r]) {
continue;
}
q.push(r);
tata[r] = x;
cif[r] = i;
if(r == 0) {
getNumber(0);
return 0;
}
}
}
in.close(); out.close();
return 0;
}