Pagini recente » Cod sursa (job #1125366) | Cod sursa (job #2821953) | Cod sursa (job #2600891) | Cod sursa (job #1961436) | Cod sursa (job #3153845)
#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;
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;
};
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[1].mini = 1;
dp[1].prec = -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;
}
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;
}
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;
int op = 0;
if( (dp[poz].prec * 10) % cmmmc != poz ) op = 1;
s.insert(s.begin(), char( op + '0' ) );
poz = dp[poz].prec;
}
fout << s << endl;
return 0;
}