Cod sursa(job #120239)

Utilizator floringh06Florin Ghesu floringh06 Data 4 ianuarie 2008 18:14:35
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <cstdio>
#include <cstdlib>

using namespace std;

#define FIN "multiplu.in"
#define FOUT "multiplu.out"
#define MAX_M 2000005

int A, B;
int M;

unsigned char ok[MAX_M];
unsigned char cf[MAX_M];

int up[MAX_M];
int c[MAX_M]; // coada

    void getsol (int c)
    {
         char sl[100] = "";
         int p = 0;
         while (c)
         {
               sl[p++] = cf[c];
               c = up[c];
         }
         for (c = p - 1; c > -1; --c) printf ("%c",  sl[c]);
         printf ("\n");
         exit (0);      
    }

    void getM ( void )
    {
         int a = A, b = B;
         while (a != b)
               if (a > b) a -= b; else b -= a;
         M = (A * B)/a;
    }

    void solve ( void )
    {
           int i, lf;
           c[lf = 1] = 1;
           cf[1] = '1';
           for (i = 1; i <= lf; ++i)
           {
                  if (ok[(c[i]*10)%M] != 1)
                  {
                                      ok[(c[i]*10)%M] = 1;
                                      c[++lf] = (c[i]*10) % M;
                                      cf[lf] = '0';
                                      up[lf] = i;
                                      if (!c[lf]) getsol(lf);
                  }
                  if (ok[(c[i]*10 + 1)%M] != 1)
                  {
                                      ok[(c[i]*10 + 1)%M] = 1;
                                      c[++lf] = (c[i]*10 + 1) % M;
                                      cf[lf] = '1';
                                      up[lf] = i;
                                      if (!c[lf]) getsol(lf);
                  }
           }
    }

    int main ()
    {
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);
        
        scanf ("%d %d", &A, &B);
        
        getM ();
        solve ();
        
        return 0;
    }