/**************************************
    算法复杂度为：O(longhta*longthb）
    longtha为乘数的位数
    longhtb为被乘数的位数
***************************************/

#include <stdio.h>
#include <string.h>
#include <conio.h>
#define LEN 1000
void mult(char [],char [],char []);
main()
{
    char op1[LEN],op2[LEN],op3[LEN*2-1];
    scanf("%s%s",op1,op2);
    mult(op1,op2,op3);
    printf("%s\n",op3);
    getch();
    return 0;   
}    
void reverse(char a[])
{
    int longth=strlen(a);
    int i;
    for(i=0;i<longth/2;i++){
        char t;
        t=a[i];
        a[i]=a[longth-i-1];
        a[longth-i-1]=t;
    }
}
void mult(char op1[LEN],char op2[LEN],char ans[LEN*2-1])
{
    char top1[LEN];
    char top2[LEN];
    strcpy(top1,op1);
    strcpy(top2,op2);
    reverse(top1);
    reverse(top2);
    int k;
    int top1s=strlen(top1);
    int top2s=strlen(top2);
    for(k=0;k<top1s+top2s;k++){
        ans[k]='0';
    }
    int i,j;
    int jw,ys;
    int longth;
    for(j=0;j<top2s;j++){
        jw=0;
        for(i=0;i<top1s;i++){
            ys=((top1[i]-'0')*(top2[j]-'0')+jw+ans[i+j]-'0')%10;
            jw=((top1[i]-'0')*(top2[j]-'0')+jw+ans[i+j]-'0')/10;
            ans[i+j]=ys+'0';
        }
        if(jw>0){
            ans[i+j]=jw+'0';
        }
    }
    longth=i+j-1;
    if(jw>0)
        ans[longth++]=jw+'0';
    ans[longth]='\0';
    reverse(ans);
}

评论