Cod sursa(job #115126)

Utilizator crawlerPuni Andrei Paul crawler Data 16 decembrie 2007 11:02:40
Problema Multiplu Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 2, Clasa a 10-a Marime 1.23 kb
#include <cstdio>

#define Nmax 2000100
#define Inf 1234567890

int v[Nmax], x[Nmax], s[Nmax];

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

int solve(int a)
{
    printf("1");   
    while(a--) printf("0");
    printf("\n");
    return 1234567890;    
}

int solve2(int a,int b)
{
    for (int i=a;i>b;--i) printf("1");
    for (int i=b;i>=0;--i) printf("0");       
    printf("\n");
    return Inf;
}

int solve1(int a,int b)
{    
    printf("1");
    for (int i=a-1;i>=0;--i) 
    if (i==b) printf("1"); else printf("0");
    printf("\n");
    return Inf;    
}


int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    
    int A,B, MOD, rest, S;
    
    scanf("%d%d", &A,&B);
    
    MOD = (A*B)/cmmdc(A,B);

    for (int i=0;i<=MOD;++i)
     x[i] = s[i] = Inf;

    rest = 1;    
    S = 0;
    for (int i=0;i<=MOD;++i)
    {
        if (rest == 0) i=solve(i);
        if (x[MOD-rest] != Inf) i=solve1(i,x[MOD-rest]); else x[rest] = i;        
        S = (S+rest)%MOD;
        if (s[S] == Inf) s[S] = i; else i=solve2(i,s[S]);       
        rest = (rest*10)%MOD;    
    }    
    
    return 0;    
}