Pagini recente » Arhiva de probleme | Cod sursa (job #3361139)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
bool imp(int div,string &nr) {
int cat = 0;
int rest = 0;
for (int i = 0; i < nr.size();++i) {
cat = cat * 10 + (nr[i] - '0');
if (cat >= div) {
cat = cat % div;
}
}
return cat == 0;
}
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
unordered_map<string, bool>m;
string solve(int a,int b) {
string start = "1";
int cmmc = a/ gcd(a, b) *b;
queue<string>q;
q.push(start);
m[start] = 1;
while (true)
{
string crtNr = q.front();
q.pop();
if (imp(cmmc, crtNr)) {
return crtNr;
}
else {
crtNr.push_back('0');
q.push(crtNr);
crtNr.pop_back();
crtNr.push_back('1');
q.push(crtNr);
}
}
}
int main()
{
int a, b;
fin >> a >> b;
fout << solve(a, b);
return 0;
}