Pagini recente » Cod sursa (job #1562773) | Cod sursa (job #260333) | Cod sursa (job #533407) | Cod sursa (job #2817480) | Cod sursa (job #1021207)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
const int MAX_M = 2000002;
int A, B;
pair < int, int > Prev[MAX_M][2];
queue < pair < int, int > > Q;
vector < char > ans1, ans2;
bool m[MAX_M][2];
inline int gcd(int a, int b) {
int r;
while(b) {
r = a % b;
a = b;
b = r;
}
return a;
}
int main() {
ifstream f("multiplu.in");
ofstream g("multiplu.out");
f >> A >> B;
int M = (A*B)/gcd(A, B);
Q.push(make_pair(1%M, 1));
m[1%M][1] = 1;
while(!Q.empty()) {
int x = Q.front().first, c = Q.front().second;
Q.pop();
int y = (x*10)%M, c1 = 0;
if(m[y][c1] == 0) {
m[y][c1] = 1;
Prev[y][c1] = make_pair(x, c);
Q.push(make_pair(y, c1));
}
y = (x*10 + 1)%M, c1 = 1;
if(m[y][c1] == 0) {
m[y][c1] = 1;
Prev[y][c1] = make_pair(x, c);
Q.push(make_pair(y, c1));
}
}
int x = 0, c = 0;
while(x != 1 || c != 1) {
ans1.push_back(c + '0');
int x1 = Prev[x][c].first, c1 = Prev[x][c].second;
x = x1, c = c1;
}
ans1.push_back('1');
x = 0, c = 1;
while(x != 1 || c != 1) {
ans2.push_back(c + '0');
int x1 = Prev[x][c].first, c1 = Prev[x][c].second;
x = x1, c = c1;
}
ans2.push_back('1');
if(ans1.size() < ans2.size())
for(int i = ans1.size() - 1; i >= 0; --i)
g << ans1[i];
else if(ans2.size() < ans1.size())
for(int i = ans2.size() - 1; i >= 0; --i)
g << ans2[i];
else {
bool ok = 1;
for(int i = ans1.size() - 1; i >= 0; --i)
if(ans2[i] < ans1[i]) {
ok = 0;
break;
}
if(ok)
for(int i = ans1.size() - 1; i >= 0; --i)
g << ans1[i];
else for(int i = ans2.size() - 1; i >= 0; --i)
g << ans2[i];
}
g << "\n";
f.close();
g.close();
return 0;
}