Cod sursa(job #163250)

Utilizator FlorinC1996Florin C FlorinC1996 Data 21 martie 2008 20:20:34
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
 #include <stdio.h>   
int i,j,k,s,p,n,m;   
bool rest[2000001],sol[2000001];   
int vine[2000001],uc[2000001];   
int coada[2000001];   
int main()   
{   
  
  
    freopen("multiplu.in","r",stdin);   
    freopen("multiplu.out","w",stdout);   
  
    scanf("%d %d",&n,&m);   
    s=n;p=m;   
    while (n%m!=0)   
    {   
        k=n%m;   
        n=m;   
        m=k;   
    }   
    k=(s*p)/m;   
  
    rest[1]=1;coada[1]=1;uc[1]=1;vine[1]=0;p=1;s=1;   
    while (!rest[0])   
    {   
        j=s;   
        for (i=p; i<=s; i++)   
        {   
            if (rest[(coada[i]*10)%k]==0)   
            {   
                rest[(coada[i]*10)%k]=1;   
                s++;   
                uc[(coada[i]*10)%k]=0;vine[(coada[i]*10)%k]=coada[i];coada[s]=(coada[i]*10)%k;   
            }   
            if (rest[0]) break;   
  
            if (rest[(coada[i]*10+1)%k]==0)   
            {   
                rest[(coada[i]*10+1)%k]=1;   
                s++;   
                uc[(coada[i]*10+1)%k]=1;vine[(coada[i]*10+1)%k]=coada[i];coada[s]=(coada[i]*10+1)%k;   
            }   
            if (rest[0]) break;   
        }   
        p=j;   
    }   
    p=0;i=0;   
    while (vine[i]!=0)   
    {   
        p++;   
        sol[p]=uc[i];   
        i=vine[i];   
    }   
    p++;sol[p]=1;   
    for (i=1; i<=p/2; i++)   
    {   
        s=sol[i];   
        sol[i]=sol[p+1-i];   
        sol[p+1-i]=s;   
    }   
    for (i=1; i<=p; i++)   
        printf("%d",sol[i]);   
    printf("\n");   
    return 0;   
}