Pagini recente » Cod sursa (job #2715441) | Cod sursa (job #2082223) | Monitorul de evaluare | Cod sursa (job #2403980) | Cod sursa (job #248589)
Cod sursa(job #248589)
using namespace std;
bool viz[1<<21],L[1<<21];
int que[1<<21],poz[1<<21];
int gcd(int x, int y)
{
for(int absente;absente;absente=x%y,x=y,y=absente);
return x;
}
#include <bitset>
void print(int x)
{
int stv[1<<15];
for(;x;)
{
stv[++stv[0]] = L[x];
x = poz[x];
}
for(int i=stv[0];i>=1;--i)
printf("%d",stv[i]);
}
int main()
{
int A,B,M;
freopen("multiplu.in","r",stdin);
freopen("multiplu.out","w",stdout);
scanf("%d %d",&A,&B);
M = A*B / gcd(A,B);
que[++que[0]] = L[1] = 1;
viz[1] = true;
for(int i=1;i<=que[0];++i)
{
int rest = que[i];
if(!rest)
{
print(i);
exit(0);
}
if(!viz[(rest * 10) % M])
{
viz[(rest * 10) % M] = true;
que[++que[0]] = (rest * 10) % M;
L[que[0]] = 0;
poz[que[0]] = i;
}
if(!viz[(rest * 10 + 1) % M])
{
viz[(rest * 10 + 1) % M] = true;
que[++que[0]] = (rest * 10 + 1) % M;
L[que[0]] = 1;
poz[que[0]] = i;
}
}
printf("non_bulan");
return 0;
}