Pagini recente » Cod sursa (job #701127) | Cod sursa (job #2095801) | Cod sursa (job #454478) | Cod sursa (job #558185) | Cod sursa (job #133194)
Cod sursa(job #133194)
/* Multiplu - Infoarena */
#include <stdio.h>
#define NMAX (1<<21)
#define INPUT "multiplu.in"
#define OUTPUT "multiplu.out"
#define max(a,b) (((a)<(b)) ? (b) : (a))
int A,B,start,end,up[NMAX],rest[NMAX],rez,i;
char Mark[NMAX],Nr[NMAX],cf[NMAX];
int cmmmc(int a, int b)
{
int i;
for (i=max(a,b);i<=a*b;i++)
if (i % a == 0 && i % b == 0)
return i;
}
int main()
{
freopen(INPUT,"r",stdin);
freopen(OUTPUT,"w",stdout);
scanf("%d%d",&A,&B);
int M=cmmmc(A,B);
up[1]=0;
rest[1]=1%M;
Mark[rest[1]]=1;
cf[1]='1';
start=1;
end=1;
for (start=1;start<=end;start++)
{
if (!rest[start]) { rez=start; break; }
if (!Mark[rest[start]*10%M])
{
Mark[rest[start]*10%M]=1;
cf[++end]='0';
up[end]=start;
rest[end]=rest[start]*10%M;
}
if (!Mark[(rest[start]*10+1)%M])
{
Mark[(rest[start]*10+1)%M]=1;
cf[++end]='1';
up[end]=start;
rest[end]=(rest[start]*10+1)%M;
}
}
while (rez)
{
Nr[++Nr[0]]=cf[rez];
rez=up[rez];
}
for (i=Nr[0];i>=1;i--)
printf("%c",Nr[i]);
fclose(stdin);
fclose(stdout);
return 0;
}