Cod sursa(job #133194)

Utilizator Darth_NiculusIvan Nicolae Darth_Niculus Data 7 februarie 2008 20:44:06
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
/* 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;
}