Pagini recente » Cod sursa (job #1605542) | Cod sursa (job #418062) | Cod sursa (job #1821284) | Cod sursa (job #2444464) | Cod sursa (job #3240440)
#include <fstream>
#include <queue>
using namespace std;
ifstream f("multiplu.in");
ofstream g("multiplu.out");
const int nmax = 2000005;
queue<int> q; //coada de resturi
int prv[nmax];
bool viz[nmax];
int n, a, b;
int cmmdc(int x, int y){
while(y != 0){
int r = x % y;
x = y;
y = r;
}
return x;
}
void reconst(int rest){
if(rest == 1){
g << 1;
return;
}
reconst(prv[rest]);
int nr = prv[rest];
if((nr * 10 + 1) % n == rest){
//avem 1
g << 1;
} else{
//avem 0
g << 0;
}
}
int main(){
f >> a >> b;
n = a * b / cmmdc(a, b);
if(n == 1){
g << 1;
return 0;
}
q.push(1);
prv[1] = 0;
viz[1] = true;
while(!q.empty()){
int rest = q.front();
q.pop();
int next_rest = (rest * 10) % n;
if(viz[next_rest] == 0){
q.push(next_rest);
prv[next_rest] = rest;
viz[next_rest] = true;
}
if(next_rest == 0){
break;
}
next_rest = (rest * 10 + 1) % n;
if(viz[next_rest] == 0){
q.push(next_rest);
prv[next_rest] = rest;
viz[next_rest] = true;
}
if(next_rest == 0){
break;
}
}
reconst(0);
}