Pagini recente » Borderou de evaluare (job #275533) | Borderou de evaluare (job #3265668) | Borderou de evaluare (job #3265368) | Borderou de evaluare (job #3365350) | Cod sursa (job #3365350)
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
//#define int long long
using namespace std;
using i128 = __int128;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
const int NMAX = 2e6;
int a, b, m;
bool visited[NMAX + 1];
int parent[NMAX + 1];
int digit[NMAX + 1];
int gcd_(int x, int y) {
while(y) {
int r = x % y;
x = y;
y = r;
}
return x;
}
int lcm_(int x, int y) {
return x / gcd_(x, y) * y;
}
void BFS() {
queue<int> q;
q.push(1);
visited[1] = true;
parent[1] = -1;
int lcm = lcm_(a, b);
while(!q.empty()) {
auto current_rest = q.front();
q.pop();
if(current_rest == 0) {
return;
}
for(int c = 0; c <= 1; c++) {
int new_rest = (current_rest * 10 + c) % lcm;
if(!visited[new_rest]) {
visited[new_rest] = true;
parent[new_rest] = current_rest;
digit[new_rest] = c;
q.push(new_rest);
}
}
}
}
void backtrack_path(int current_rest) {
if(parent[current_rest] == -1) {
fout << 1;
return;
}
backtrack_path(parent[current_rest]);
fout << digit[current_rest];
}
int main() {
fin >> a >> b;
BFS();
backtrack_path(0);
return 0;
}