Pagini recente » Cod sursa (job #2656172) | Cod sursa (job #2066962) | Cod sursa (job #997902) | Cod sursa (job #700316) | Cod sursa (job #116309)
Cod sursa(job #116309)
#include <stdio.h>
#define NMAX 2000000
int a, b, m, c;
int viz[250000];
typedef struct
{
char c;
int r, p;
}QUADA;
QUADA q[NMAX];
int cmmdc(int a, int b)
{
int r;
while (b)
{
r = a %b;
a = b;
b = r;
}
return a;
}
void afisare(int i)
{
if (i!=0)
{
afisare(q[i].p);
printf("%c",q[i].c);
}
}
void rezolv()
{
int st, dr, ex = 1, r;
st = dr = 1;
q[st].c = '1';
q[st].p = 0;
q[st].r = 1 % m;
viz[q[st].r>>3] |=(1<<(q[st].r&7));
while ( st <= dr && ex)
{
r = (q[st].r*10 ) % m;
if ( !(viz[r>>3] & (1<<(r&7)) ) )
{
dr++;
q[dr].r = r;
q[dr].p = st;
q[dr].c = '0';
viz[q[dr].r>>3] |= 1<<(q[dr].r&7);
if (q[dr].r == 0)
ex = 0;
}
if ( ex)
{
r = (q[st].r*10 + 1) % m;
if ( !(viz[r>>3] & (1<<(r&7)) ) )
{
dr++;
q[dr].r = r;
q[dr].p = st;
q[dr].c = '1';
viz[q[dr].r>>3] |= 1<<(q[dr].r&7);
if (q[dr].r == 0)
ex = 0;
}
}
st++;
}
if ( !ex)
afisare(dr);
}
int main()
{
freopen("multiplu.in", "r", stdin);
freopen("multiplu.out", "w", stdout);
scanf("%d %d", &a, &b);
c = cmmdc(a,b);
m = (a*b)/c;
rezolv();
return 0;
}