Pagini recente » Cod sursa (job #2721120) | Cod sursa (job #207106) | Cod sursa (job #2606874) | Cod sursa (job #813948) | Cod sursa (job #2785758)
#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 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;
int currRest;
while(!q.empty() && !found){
currRest = q.front();
q.pop();
choice(q, currRest, 0, found);
choice(q, currRest, 1, found);
}
}
int main(){
int a, b, c;
in>>a>>b;
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];
in.close();
out.close();
return 0;
}