Cod sursa(job #1766381)

Utilizator silkMarin Dragos silk Data 27 septembrie 2016 21:39:51
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <cstdio>
#include <cstring>
#define NMax 2000000
#define DMax 30

int rest[DMax+1];
char is[NMax+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 && !is[j] )
        {
            if( j+v > X )
                if( !dp[j+v-X] ) dp[j+v-X] = i, is[j+v-X] = 1;
                else;
            else if( !dp[j+v] ) dp[j+v] = i, is[j+v] = 1;
        }

        memset(is, 0, sizeof(is));
    }

    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;
}