压位高精乘法

解题思路:朴素的高精度乘法是一位一位存数的，而用于存储结果的int(我用的是short)数组中每一个元素显然能存储比9大得多的数，这就造成很多浪费。因而改为每次都进行k位数相乘，最终结果的每一个元素为k位数。这种做法不仅充分利用了数据范围，还大大减小时间复杂度的常数。
下面的代码实现了2位压位高精
注意事项:注释里有

参考代码:

//k位压位高精可以看成10^k进制，因此最终模数改为10^k
int add(short *num1,short *num2,int len1,int len2) {
    int f=0; //进位标记。
    int maxlen=max(len1,len2);
    for(int i=0; i<maxlen; i++) {
        int now=num1[i]+num2[i]+f;
        res[i]=now%100;
        f=now/100;
    }
    if(f)    res[maxlen]=1;
    return maxlen;
}

int mul(char *s1,char *s2) {
    int len1=strlen(s1),len2=strlen(s2),res_len=0;
    reverse(s1,s1+len1);
    reverse(s2,s2+len2);
    static short tmp[M+M]; //临时存储结果
    //此处i每次加2，因此不再代表最后补0的位数，需要另一个计数器统计0的位数
    for(int i=0,zero=0; i<len2; i+=2,zero++) {
        int jw=0,cnt=0; //由于j每次加2，所以还要额外设置计数器cnt
        if(zero!=0)    tmp[zero-1]=0;  //上一位清零
        for(int j=0; j<len1; j+=2) {
            //应防止最高位不够用
            int fac1=(s2[i]-'0')+10*(max(s2[i+1],'0')-'0'),fac2=(s1[j]-'0')+10*(max(s1[j+1],'0')-'0');  
            int now=fac1*fac2+jw;
            //tmp也是倒序，最后留i个0
            tmp[zero+cnt++]=now%100;
            jw=now/100;
        }
        //处理当前最高位
        tmp[zero+cnt]+=jw;
        res_len=add(res,tmp,res_len,zero+cnt+((tmp[zero+cnt]!=0)?1:0));
    }
    if(res[res_len]!=0)       res_len++;
    return res_len;
}
//输出注意：除最高位外，不足2位的补0，方法：printf("%02hd",res[i]);