Cod sursa(job #139166)

Utilizator crawlerPuni Andrei Paul crawler Data 19 februarie 2008 19:41:43
Problema Multiplu Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <stdio.h>

int cmmdc(int a,int b)
{
    if (b ==0) return a;
    return cmmdc(b,a%b);    
}

#define Nmax 2000100

int q[Nmax];
bool c[Nmax];
int l[Nmax];

void reconstruct(int x)
{
     if (l[x] != 0) reconstruct(l[x]);
     printf("%d", c[x]);     
}

int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    
    int a,b;
    
    scanf("%d%d",&a,&b);
    
    a=(a*b)/cmmdc(a,b);
    
    q[1] = 1;
    c[1] = 1;
    l[1] = 0;
    
    int st,dr;
    st = 0;
    dr = 1;
    
    while (1)
    {
          ++st;
          b = (q[st]*10)%a;
          ++dr;
          q[dr] = b;
          c[dr] = 0;
          l[dr] = st;
          if (b == 0) 
          {
             reconstruct(dr);
             return 0;                   
          }
          b = (b+1)%a;
          ++dr;
          q[dr] = b;
          c[dr] = 1;
          l[dr] = st;
          if (b == 0) 
          {
             reconstruct(dr);
             return 0;                   
          }             
    }   
    
    return 0;    
}