Pagini recente » Cod sursa (job #3330678) | Cod sursa (job #1247088) | Cod sursa (job #3352617) | Cod sursa (job #3312747) | Cod sursa (job #3306169)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
const int Xmax = 2000005;
int A, B, X;
queue<int> Q; /// in coada adaugam resturile prin X
vector<int> prv(Xmax, -1); // prv[x] = restul cu care am ajuns in x
// prin adaugarea cifrei 0 sau 1
int cmmdc(int nr1, int nr2){
while(nr1 != nr2){
if(nr1 > nr2){
nr1 -= nr2;
}
else{
nr2 -= nr1;
}
}
return nr1;
}
void reconst(int rest){
if(rest == 1){
fout << 1;
return;
}
reconst(prv[rest]);
if((prv[rest] * 10) % X == rest){
fout << 0;
}
if((prv[rest] * 10 + 1) % X == rest){
fout << 1;
}
}
int main()
{
fin >> A >> B;;
X = (A * B) / cmmdc(A, B);
prv[1] = 1;
Q.push(1);
while(!Q.empty()){
int rest = Q.front();
Q.pop();
if(rest == 0){
break;
}
int r0 = (rest * 10) % X;
if(prv[r0] == -1){
Q.push(r0);
prv[r0] = rest;
}
int r1 = (rest * 10 + 1) % X;
if(prv[r1] == -1){
Q.push(r1);
prv[r1] = rest;
}
}
reconst(0);
return 0;
}