Pagini recente » Cod sursa (job #627526) | Rating Andrei Ignat (Andrei_Ignat) | Cod sursa (job #791657) | Cod sursa (job #643329) | Cod sursa (job #118278)
Cod sursa(job #118278)
#include <stdio.h>
#define NMAX 2000000
int a, b, m, c;
char viz[250000];
typedef struct
{
char c;
int r, p;
}QUADA;
QUADA q[NMAX];
int cmmdc(int u, int v)
{
int k, dif, m = 0;
if ( u == 0 || v == 0)
return u|v;
for ( k = 0; ( (u|v)&1 )==0; k++)
{
u>>=1;
v>>=1;
}
while ( (u&1) == 0)
u>>=1;
do
{
while ( ( v&1) == 0 )
v>>=1;
if ( u <= v)
v = v - u;
else
{
dif = u - v;
u = v;
v = dif;
}
}while (v);
m = m | (1<<k);
return m * u;
}
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;
}