Pagini recente » Cod sursa (job #856495) | Cod sursa (job #1814667) | Cod sursa (job #2439309) | Cod sursa (job #2504771) | Cod sursa (job #1521502)
#include <iostream>
#include <fstream>
#include <string>
#include <set>
#include <queue>
#include <vector>
#define DN 2000005
using namespace std;
int pos[DN], digit[DN], parent[DN];
int gcd(int a, int b) {
for(int r; b; r = a % b, a = b, b = r);
return a;
}
int main() {
int a, b;
//freopen("input.txt", "r", stdin);
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
fin >> a >> b;
int lcm = a * b / gcd(a, b);
pos[1] = 0;
queue <int> q;
q.push(1);
digit[1] = 1;
parent[1] = 0;
while(!q.empty()) {
int elem = q.front();
q.pop();
int x = (elem * 10) % lcm;
if(!pos[x]){
pos[x] = 1;
digit[x] = 0;
parent[x] = elem;
if(x == 0)
break;
q.push(x);
}
int y = (x + 1) % lcm;
if(!pos[y]) {
pos[y] = 1;
digit[y] = 1;
parent[y] = elem;
if(y == 0)
break;
q.push(y);
}
}
vector <short> res;
int crt = 0;
while(parent[crt] != 0) {
res.push_back(digit[crt]);
crt = parent[crt];
}
res.push_back(1);
for(vector <short>::reverse_iterator it = res.rbegin(); it != res.rend(); ++it)
fout << *it;
return 0;
}