Pagini recente » Cod sursa (job #1272393) | Cod sursa (job #2465778) | Cod sursa (job #1638101) | Cod sursa (job #2242486) | Cod sursa (job #1704124)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <bitset>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
int cmmdc(int a, int b)
{
if(b == 0)
return a;
return cmmdc(b,a%b);
}
int t[2000001];
int nrc[2000001];
bitset<2000001> c;
queue<int> Q;
void fa(int& r, int& x,const int cif)
{
nrc[r] = nrc[x] + 1;
t[r] = x;
c[r] = cif;
Q.push(r);
}
void afis(int x)
{
if(x != 1)
afis(t[x]);
fout<<c[x];
}
int main()
{
int a, b;
fin>>a>>b;
int div = a*b/cmmdc(a,b);
Q.push(1);
c[1] = 1;
nrc[1] = 1;
bool found = false;
int rest1, rest2;
while(!Q.empty() && !found)
{
int x = Q.front();
if(x == 0)
{
afis(x);
found = true;
continue;
}
Q.pop();
rest1 = (x*10)%div;
rest2 = (x*10+1)%div;
if(nrc[x] + 1 < nrc[rest1] || nrc[rest1] == 0)
fa(rest1, x, 0);
if(nrc[x] + 1 < nrc[rest2] || nrc[rest2] == 0)
fa(rest2, x, 1);
}
return 0;
}