Pagini recente » Cod sursa (job #1151471) | Cod sursa (job #78728) | Cod sursa (job #3222444) | Cod sursa (job #2081282) | Cod sursa (job #1540255)
#include <cstdio>
#include <deque>
using namespace std;
const int maxN = 2e6;
class Nod {
public:
int cif, tata, rest;
Nod(int _cif = 0, int _tata = 0, int _rest = 0) :
cif(_cif), tata(_tata), rest(_rest) { }
};
Nod C[maxN + 1];
int first, last;
int f[maxN + 1];
int gcd(int a, int b) {
if(!b)
return a;
return gcd(b, a % b);
}
deque<int> sol;
int main() {
freopen("multiplu.in", "r", stdin);
freopen("multiplu.out", "w", stdout);
int A, B;
scanf("%d %d", &A, &B);
int prod = A * B;
if(prod == 1) {
puts("1");
return 0;
}
int lcm = prod / gcd(A, B);
C[++ last] = Nod(1, -1, 1);
first = 1;
while(first <= last) {
int val = C[first].rest;
if(!f[(val * 10) % lcm]) {
C[++ last] = Nod(0, first, (val * 10) % lcm);
if((val * 10) % lcm == 0)
break;
++ f[(val * 10) % lcm];
}
if(!f[(val * 10 + 1) % lcm]) {
C[++ last] = Nod(1, first, (val * 10 + 1) % lcm);
if((val * 10 + 1) % lcm == 0)
break;
++ f[(val * 10) + 1 % lcm];
}
++ first;
}
Nod x = C[last];
while(x.tata != -1) {
sol.push_front(x.cif);
x = C[x.tata];
}
sol.push_front(1);
for(auto it = sol.begin(); it != sol.end(); ++ it)
printf("%d", *it);
printf("\n");
return 0;
}