Pagini recente » Cod sursa (job #2128413) | Cod sursa (job #2791286) | Cod sursa (job #2407215) | Cod sursa (job #581171) | Cod sursa (job #2785834)
#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, tmp;
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;
tmp.clear();
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;
string ans;
ans.reserve(1000);
while (true) {
ans.push_back('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)
ans.push_back('0');
p = urm;
}
while (p > 0)
ans.push_back('0'), --p;
cout << ans;
cin.close();
cout.close();
return 0;
}