Pagini recente » Cod sursa (job #83880) | Cod sursa (job #2613444) | Cod sursa (job #2201836) | Cod sursa (job #87842) | Cod sursa (job #2785752)
#include <fstream>
#include <queue>
std::ifstream in("multiplu.in");
std::ofstream out("multiplu.out");
const int N = 2e6 + 1;
int previous[N], number[N];
bool digit[N];
int a, b, lcm;
inline void choice(std::queue<int> &q, int &currRest, bool d, bool &found){
int newRest = (currRest * 10 + d) % lcm;
if(previous[newRest] != 0) return;
q.push(newRest);
previous[newRest] = currRest;
digit[newRest] = d;
found = (newRest==0);
}
void bfs(){
std::queue<int> q{{1}};
digit[1] = 1;
previous[1] = -1;
bool found = false;
while(!q.empty() && !found){
int currRest = q.front();
q.pop();
choice(q, currRest, 0, found);
choice(q, currRest, 1, found);
}
}
int main(){
in>>a>>b;
int c;
lcm = a*b;
while(b){
c = a%b;
a = b;
b = c;
}
lcm /= a;
int currRest = 0, cnt=0;
bfs();
while(currRest >= 0){
number[cnt++] = digit[currRest];
currRest = previous[currRest];
}
for(int i=cnt-1;i>=0;--i)
out<<number[i];
}