Pagini recente » Cod sursa (job #1985993) | Cod sursa (job #1156116) | Cod sursa (job #609231) | Cod sursa (job #2562636) | Cod sursa (job #1766381)
#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;
}