Pagini recente » Cod sursa (job #3274261) | Cod sursa (job #3165778) | Cod sursa (job #269053) | Cod sursa (job #2282708) | Cod sursa (job #2966662)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("multiplu.in");
ofstream cout("multiplu.out");
const int NMAX = 2e6;
vector <char> inf(35);
struct p{
vector <char> x;
};
p min_num[NMAX + 1];
queue <vector <char>> q;
int cmmmc;
int cmmdc(int x, int y){
int r = 0;
while(y){
r = x % y;
x = y;
y = r;
}
return x;
}
int modulo(vector <char> x, int p){
int ans = 0;
for(auto e : x){
ans = ans * 10 + (e - 48);
ans %= p;
}
return ans;
}
bool mai_mare(vector <char> a, vector <char> b){
if(a.size() < b.size())
return 0;
if(a.size() > b.size())
return 1;
for(int i = 0; i < a.size(); i++)
if(a[i] < b[i])
return 0;
return 1;
}
void bfs(vector <char> x){
q.push(x);
min_num[1].x.push_back('1');
while(!q.empty()){
vector <char> x = q.front();
q.pop();
int rm = modulo(x, cmmmc);
min_num[rm].x = x;
if(rm == 0)
return;
rm *= 10;
rm %= cmmmc;
x.push_back('0');
if(mai_mare(min_num[rm].x, x)){
min_num[rm].x = x;
q.push(x);
}
x.pop_back();
x.push_back('1');
rm = rm * 10 + 1;
rm %= cmmmc;
if(mai_mare(min_num[rm].x, x)){
min_num[rm].x = x;
q.push(x);
}
}
}
int main(){
int x = 0, y = 0;
cin >> x >> y;
if(x == y){
cout << x;
return 0;
}
cmmmc = x * y / cmmdc(x, y);
for(int i = 0; i <= 30; i++)
inf[i] = '9';
for(int i = 0; i < cmmmc; i++)
min_num[i].x = inf;
vector <char> temp;
temp.push_back('1');
bfs(temp);
for(auto e : min_num[0].x)
cout << e;
}