Pagini recente » Cod sursa (job #1472592) | Cod sursa (job #1136498) | Cod sursa (job #285844) | Cod sursa (job #2856976) | Cod sursa (job #3286892)
#include <bits/stdc++.h>
using namespace std;
ifstream f("multiplu.in");
ofstream g("multiplu.out");
/*
strategie de rezolvare:
cmmmc(a, b) = a * b / cmmdc(a, b)
cmmdc - euclid
construim cel mai mic multiplu comun format doar din 0 si 1
folosesc BFS pentru a explora toate numerele posibile care sa fie formate din 0 si 1
ma bazez pe resturile mod cmmdc(a, b) pentru a verifica daca am gasit un multiplu corect
*/
int a, b, n, p, rest, x, k;
int prec[2000005];
char str[2000005];
bitset<2000005> cf, dist;
queue<int> q;
int main()
{
f >> a >> b;
p = a * b;
while (a != b) {
if (a > b) a -=b;
else b-=a;
}
n = p / a; // cmmmc(a, b);
// bfs pentru a gasi multiplu format doar din cifre de 0 si 1
// folosim bfs pentru a genera multiplii de n folosind doar 0 si 1
// pastram predecesorii pentru a reconstrui numarul final
dist[1] = 1; // marchez restul 1 ca vizitat
q.push(1);
cf[1] = 1; // cifra care a dus la acest rest
prec[1] = -1; // nu are predecesor
while (dist[0] == 0) { // cautam primul multiplu de n
rest = q.front();
q.pop();
for (int i = 0; i <= 1; i++) { // adaugam 0 si 1
x = (rest * 10 + i) % n;
if (dist[x] == 0) {
dist[x] = 1;
cf[x] = i; // stochez cifra folosita
prec[x] = rest; // stocam predecesorul
q.push(x);
}
}
}
// reconstruim solutia invers
x = 0;
while (x != -1) {
k++;
str[k] = cf[x] + '0'; // adaug cifra
x = prec[x]; // ne deplasam inapoi
}
for (k; k > 0; k--) { // scriem in fisier in ordinea corecta
g << str[k];
}
return 0;
}