Cod sursa(job #1766371)

Utilizator silkMarin Dragos silk Data 27 septembrie 2016 21:28:49
Problema Multiplu Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <cstdio>
#define NMax 2000000
#define DMax 30

int rest[DMax+1];
int dp[NMax+1];

int main(){
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);

    int i,j,v,A,B,X,a,b,r;

    scanf("%d %d",&A,&B);

    if(A==1 && B==1) { printf("1\n"); return 0; }

    a = A;
    b = B;
    while(b) { r = a%b; a = b; b = r; }
    X = A*B/a;

    dp[0] = DMax+1;
    for(v = 1, i = 1; !dp[X]; ++i, v*=10)
    {
        rest[i] = ( v = v % X );
        for(j = X; j >= 0; --j)
        if( dp[j] > 0 )
        {
            if( j+v > X )
                if( !dp[j+v-X] ) dp[j+v-X] = -i;
                else;
            else if( !dp[j+v] ) dp[j+v] = -i;
        }

        for(j = 0; j <= X; ++j)
        if( dp[j] < 0 ) dp[j] *= -1;
    }

    r = 0;
    v = X;

    while(v)
    {
        a = dp[v];

        if( v - rest[a] < 0 ) v = X+v-rest[a];
        else v = v-rest[a];

        b = dp[v];

        ++r;
        printf("1");

        if(v)
            for(i = a-1; i > b; --i) { printf("0"); ++r; }
    }

    for(i = 1; i <= dp[X]-r; ++i) printf("0");
    printf("\n");



return 0;
}