Pagini recente » Cod sursa (job #1202142) | Cod sursa (job #2039112) | Cod sursa (job #1549755) | Cod sursa (job #1214671) | Cod sursa (job #1101503)
#include <cstdio>
#include <vector>
#include <queue>
#define NMAX 2000007
using namespace std;
struct Multiplu{
int c;
int r;
};
vector< bool > Ans;
queue< Multiplu > Sol;
int Prev[NMAX];
bool Cif[NMAX], Ap[NMAX], V[NMAX];
Multiplu Aux;
inline int gcd(int a, int b){
if(! b)
return a;
return gcd(b, a % b);
}
int main(){
int a = 0, b = 0, m = 0;
freopen("multiplu.in", "r", stdin);
freopen("multiplu.out", "w", stdout);
scanf("%d %d", &a, &b);
m = a * b / gcd(a, b);
Aux.c = 1;
Aux.r = 1 % m;
Sol.push(Aux);
Prev[Aux.r] = 1;
Cif[Aux.r] = 1;
while(! Sol.empty()){
Aux = Sol.front();
Sol.pop();
Multiplu NewAux;
for(int i = 0; i <= 1; ++i){
NewAux.c = i;
NewAux.r = (Aux.r * 10 + i) % m;
if(Ap[NewAux.r] == 0){
Ap[NewAux.r] = 1;
Prev[NewAux.r] = Aux.r;
Cif[NewAux.r] = i;
Sol.push(NewAux);
}
}
}
int c = 0, NR = 0;
while(c != 1){
V[++NR] = Cif[c];
c = Prev[c];
}
if(m != 1)
V[++NR] = 1;
for(int i = NR; i >= 1; --i)
printf("%d", V[i]);
printf("\n");
return 0;
}