C++实现大数除法

题外话

大数除法无疑是大数操作里最麻烦的一项，写大数不实现除法无异于画龙无鳞。

思路

最原始的，脑子最容易冒出来的思路，是一下一下的减，看能累计减多少次，最后的总次数就是结果，但这样的效率实在太慢。但我们可以一次性减去 除数的1，10，100，1000倍，只要它在当前倍数下比被除数小。
例如 1210 3 ，121大于300，我们直接剪去300，给结果加100，这样的话，减的次数会大大减小。
基本的思想就是这样，具体细节见代码，这里不再赘述

进一步优化的方案

上文所述，时间复杂度最坏情况是 9(n-m)*m (解的最坏位数为n-m位，每一位的解最多要减9次，每剪一次需要O(m))
当n,m为万级时，效率仍不尽人意。看大牛代码，发现有这样一个优化的方案。
我们正常用数组来表式大数时，是按照10进制来保存的，我们可以用比如10000来保存，那么长度为n的大数，长度就变为n/4
时间复杂度为原来的1/8

代码(未优化)

#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <string.h>
#include <set>
#include <stack>
#include <stdlib.h>
#include <time.h>

using namespace std;

const int N = 100009;

struct Node
{
    int d[N];
    int len;

    Node() {memset(d, 0, sizeof(d));len=1;}
    Node(char *s)
    {
        memset(d, 0, sizeof(d));
        len = strlen(s);
        int i = 0;
        while(s[i] != '\0')
        {
            d[len-i-1] = s[i] - '0';
            ++i;
        }
    }

    int cmp(const Node &t)
    {
        int l = this->len - t.len;
        if(l < 0)
            return -1;

        int i;
        for(i=t.len-1;i>=0;i--)
        {
            if(this->d[i+l] < t.d[i])
                break;
            else if(this->d[i+l] > t.d[i])
            {
                return l;
            }
        }
        if(i < 0)
            return l;
        return l-1;
    }

    void change(int pos)
    {
        this->d[pos] += 1;
        int i = pos;
        while(this->d[i] > 9)
        {
            this->d[i] -= 10;
            this->d[i+1]++;
            ++i;
        }
        if(i+1 > this->len)
            this->len = i+1;
    }

    Node operator / (const Node &t)
    {
        Node ans;
        while(1)
        {
            int p = this->cmp(t);
            if(p == -1)
                break;
            else
            {
                ans.change(p);
                for(int i=0;i<t.len;i++)
                {
                    this->d[i+p+1]--;
                    this->d[i+p] = this->d[i+p]+10-t.d[i];
                    if(this->d[i+p] > 9)
                    {
                        this->d[i+p] -= 10;
                        this->d[i+1+p]++;
                    }
                }
                while(this->len > 1 && this->d[this->len - 1] == 0)
                    this->len--;
            }
        }

        return ans;
    }

};

char str[N];

int main()
{
    scanf("%s",str);
    Node a(str);
    scanf("%s",str);
    Node b(str);
    Node ans = a / b;
    for(int i=ans.len-1;i>=0;i--)//商
        printf("%d",ans.d[i]);
    printf("\n");
    for(int i=a.len-1;i>=0;i--)//模
        printf("%d",a.d[i]);
    printf("\n");
    return 0;
}