Pagini recente » Cod sursa (job #3270055) | Cod sursa (job #123501) | Cod sursa (job #235014) | Cod sursa (job #1771573) | Cod sursa (job #3211602)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
const int Nmax= 200005;
queue<int> q;
int ant[Nmax],D,A,B,i,j;
vector<int> sol;
//Vom pastra resturilein queue ptc numarul poate sa depaseasca chiar si long long
//Vom face un anterior[] pt reconstituire
int cmmdc(int a,int b)
{
if(b==0) return a;
return cmmdc(b, a%b);
}
void reconst(int val)
{
int prv = ant[val]; //9 - 0
if(prv * 10 % D == val) sol.push_back(0);
else sol.push_back(1);
if(prv == -2) return;
reconst(prv); //1 9 0
}
int main()
{
fin>>A>>B;
D = A*B / cmmdc(A,B);
q.push(1);
int val = 1;
for(i=0; i<=D; i++)
ant[i] = -1; // merge si ca un vector de visited[]
ant[1] = -2; //conditie stop reconst()
while(!q.empty()) //merg pana am primul rest de 0
{
val = q.front();
q.pop();
int rest1 = (val * 10)%D;
int rest2 = (val*10 +1) %D;
if(ant[rest1]== -1) //daca nu am mai intalnit restul
q.push(rest1), ant[rest1] = val;
if(ant[rest2] == -1)
q.push(rest2), ant[rest2] = val;
}
reconst(0);
for(i=sol.size()-1; i>=0; i--) //trb sa o luam invers
{
fout<<sol[i];
}
return 0;
}