Pagini recente » Cod sursa (job #819881) | Cod sursa (job #2771217) | Cod sursa (job #3229613) | Cod sursa (job #1241782) | Cod sursa (job #1766371)
#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;
}