Pagini recente » Cod sursa (job #561872) | Cod sursa (job #2986172) | Cod sursa (job #943830) | Cod sursa (job #3185143) | Cod sursa (job #2785829)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 2e6 + 5;
bool viz[N];
int ant[N], p10[N];
vector<int> v;
bool check(int x) {
while (x) {
if (x % 10 > 1)
return false;
x /= 10;
}
return true;
}
int main() {
ifstream cin("multiplu.in");
ofstream cout("multiplu.out");
int a, b, x;
cin >> a >> b;
x = a * b / __gcd(a, b);
p10[0] = viz[1] = 1;
v.push_back(1);
for (int i = 1; i <= N; ++i) {
p10[i] = (long long) p10[i - 1] * 10 % x;
vector<int> tmp;
for (auto j : v) {
int nou = (j + p10[i]) % x;
if (!viz[nou]) {
viz[nou] = true;
tmp.push_back(nou);
ant[nou] = i;
}
}
for (auto j : tmp)
v.push_back(j);
if (!viz[p10[i]]) {
viz[p10[i]] = true;
v.push_back(p10[i]);
ant[p10[i]] = i;
}
if (viz[0]) break;
}
int p = ant[0], s = 0;
while (true) {
cout << "1";
s -= p10[p];
if (s < 0) s += x;
if (!s)
break;
int urm = ant[s];
for (int i = 0; i < p - urm - 1; ++i)
cout << "0";
p = urm;
}
while (p > 0)
cout << "0", --p;
cin.close();
cout.close();
return 0;
}