Pagini recente » Cod sursa (job #364175) | Cod sursa (job #2298701) | Cod sursa (job #1768747) | Cod sursa (job #1014833) | Cod sursa (job #2323818)
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
std::ifstream in("multiplu.in") ;
std::ofstream out("multiplu.out") ;
const int MAX = 2000005 ;
int a, b, lcm ;
int curr ;
std::vector <int> rez ;
int cif[MAX], ult[MAX] ;
bool avem[MAX] ;
std::queue < std::pair <int, int> > Q ;
inline int modCalc(int a, int b) {
while (a >= b)
a -= b ;
return a ; }
int gcd(int a, int b) {
if (b == 0)
return a ;
return gcd(b, modCalc(a, b)) ; }
signed main() {
in >> a >> b ;
if (a + b == 1) {
out << 1 ;
return 0 ; }
lcm = a * b / gcd(a, b) ;
Q.push({1, 0 }) ;
avem[1] = 0 ;
ult[curr] = -1 ;
cif[curr] = 1 ;
ll deacolo = -1 ;
while (!Q.empty()) {
std::pair <int, int> nod = Q.front() ;
Q.pop() ;
int r = nod.first, t = nod.second ;
if (!avem[modCalc(r * 10, lcm)]) {
curr++ ;
Q.push({modCalc(r * 10, lcm), curr }) ;
avem[modCalc(r * 10, lcm)] = 1 ;
ult[curr] = t ;
cif[curr] = 0 ;
if (modCalc(r * 10, lcm) == 0) {
deacolo = curr ;
break ; } }
if (!avem[modCalc(r * 10 + 1, lcm)]) {
curr++ ;
Q.push({modCalc(r * 10 + 1, lcm), curr }) ;
avem[modCalc(r * 10 + 1, lcm)] = 1 ;
ult[curr] = t ;
cif[curr] = 1 ;
if (modCalc(r * 10 + 1, lcm) == 0) {
deacolo = curr ;
break ; } } }
while (deacolo != -1) {
rez.pb(cif[deacolo]) ;
deacolo = ult[deacolo] ; }
std::reverse(rez.begin(), rez.end()) ;
for (int x=0;x<rez.size();++x)
out << rez[x] ;
return 0 ;
}