Pagini recente » Cod sursa (job #1794218) | Cod sursa (job #1337488) | Cod sursa (job #837966) | Cod sursa (job #261063) | Cod sursa (job #3153844)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
//ifstream fin("/Users/jdev/Documents/ProgrameInfoC++/Multiplu/multiplu.in");
//ofstream fout("/Users/jdev/Documents/ProgrameInfoC++/Multiplu/multiplu.out");
long long int a, b;
long long int mini = 2000000000000000000ll;
void build(long long int v){
if(v <= 2000000000000000000ll){
if( v > 0 && v % a == 0 && v % b == 0 ) mini = min(mini, v);
if(v > 0) build(v * 10);
build(v * 10 + 1);
}
}
int cmmdc(int a, int b){
int c = 0;
while(b > 0){
c = a % b;
a = b;
b = c;
}
return a;
}
struct poz{
int mini, prec, op;
};
int main(){
cin.tie(0);ios::sync_with_stdio(0);
//1.
//2.
fin >> a >> b;
//3.
//cout << "a = " << a << " b = " << b << endl;
//cout << "cmmdc = " << cmmdc(a, b) << endl;
int cmmmc = (a / cmmdc(a, b)) * b;
//cout << "cmmmc = " << cmmmc << endl;
poz dp[cmmmc];
for(int i = 0; i < cmmmc; i++){
dp[i].mini = INT_MAX;
dp[i].prec = -1;
dp[i].op = 1;
}
dp[1].mini = 1;
dp[1].prec = -1;
dp[1].op = 1;
queue<int> q;
q.push(1);
while(!q.empty()){
int t = q.front();
q.pop();
int r = (t * 10) % cmmmc;
if(dp[r].mini > dp[t].mini + 1){
dp[r].mini = dp[t].mini + 1;
dp[r].prec = t;
dp[r].op = 0;
}
if(r == 0) break;
q.push(r);
r = (t * 10 + 1) % cmmmc;
if(dp[r].mini > dp[t].mini + 1){
dp[r].mini = dp[t].mini + 1;
dp[r].prec = t;
dp[r].op = 1;
}
if(r == 0) break;
q.push(r);
}
//cout << "facem din " << dp[0].mini << " cifre " << endl;
string s;
int poz = 0;
for(int i = 0; i < dp[0].mini; i++){
//cout << "poz = " << poz << endl;
s.insert(s.begin(), char( dp[poz].op + '0' ) );
poz = dp[poz].prec;
}
fout << s << endl;
return 0;
}