Cod sursa(job #118222)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 23 decembrie 2007 19:02:21
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <stdio.h>

#define maxx 2000010

int n,l;
int A,B;
char c[maxx];
int s[maxx],from[maxx];

int GCD(int a,int b)
{
    int aux;
    
    while (b)
    {
        aux=a%b;
        a=b;
        b=aux;
    }
    
    return a;
}

int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    
    scanf("%d %d ",&A, &B);
    
    int x,i;
    
    n=A*B/GCD(A,B);
    
    l=1;
    s[l]=1;
    c[l]=1;
    
    for (i=1;i<=l;i++)
    {
        x=(s[i]*10) % n;
        if (c[x]==0) 
        {
            s[++l]=x;
            from[x]=s[i];
            c[x]=1;
            if (x==0) break;
        }
        
        x++;
        if (x==n) x=0;

        if (c[x]==0) 
        {
            s[++l]=x;
            from[x]=s[i];
            c[x]=2;
            if (x==0) break;
        }
    }
    
    l = x =0;
    
    while (x!=1)
    {
        s[++l]=c[x]-1;
        x=from[x];
    }
    
    s[++l]=1;
    for (i=l;i>0;i--) printf("%d",s[i]);
    printf("\n");
    
    return 0;
}