[数据结构与算法]POJ1001 求高精度幂 （分治高精度大数相乘）

总体思路：

高精度大数乘法
需要记录小数点位置
需要使用大数相乘
只是考验能否使用大数相乘

大整数乘法可以模拟乘法运算写
也可以使用分治写法
分治可以优化XY=AC2^N [(A-B)(D-C)+AC+BD]2^n/2+BD
时间复杂度可以优化到T(n) = O(n^log2(3) ) = O(n^1.59 )

有几个特判也需要注意，其他没什么

POJ使用to_string 过不了也不知道为啥必须手写
POJ使用stoi过不了也不知道为啥必须手写
POJ不能使用万能头文件
注意去除前后的0

另外java有大数类，可以直接得到结果

#include <algorithm>
#include <iostream>
#include <string>

using namespace std;
string BigNumberAccumulate(string a, string b) //大数相加
{
  //比较长度，长的放前面,且顺便将长度也交换
  int LenA = a.length();
  int LenB = b.length();
  if (LenB > LenA)
  {
    string temp = a;
    a = b;
    b = temp;
    int tempLen = LenA;
    LenA = LenB;
    LenB = tempLen;
  }

  int D = LenA - LenB; //两者长度差

  int JinZi = 0, i; //需要进的数
  //从后往前模拟加法运算
  for (i = LenB - 1; i >= 0; i--)
  {
    int temp = (a[i + D] - '0') + (b[i] - '0') + JinZi; //当前位下a,b和
    JinZi = 0;                                          //进制归0
    if (temp >= 10)
    {
      JinZi++;
      temp -= 10;
    }
    a[i + D] = temp + '0';
  }
  while (i >= 0 - D && JinZi == 1)
  {
    int temp = (a[i + D] - '0') + JinZi;
    JinZi = 0;
    if (temp >= 10)
    {
      JinZi++;
      temp -= 10;
    }
    a[i + D] = temp + '0';
    i--;
  }
  if (JinZi == 1)
    a = "1" + a;
  while (a[0] == '0')
    a = a.substr(1, a.length() - 1);
  return a;
}
string Pointclear(string temp, int Pos) //清除小数点
{
  if (Pos != -1)
    return temp.erase(Pos, 1);
  else
    return temp;
}
string Tostring(int n)      //POJ使用to_string 过不了也不知道为啥必须手写
{
  string ret = "";
  while (n)
  {
    ret += n % 10 + '0';
    n /= 10;
  }
  reverse(ret.begin(), ret.end());
  return ret;
}
int Stoi(string s) //POJ使用Stoi过不了也不知道为啥必须手写
{
  int ret = 0;
  for (int i = 0; i < s.length(); i++)
  {
    ret = ret * 10 + s[i] - '0';
  }
  return ret;
}


string D_ADD(string x, string y) //大数相乘 分治写法 时间复杂度 n^1.59
{
  //补零
  int LenX = x.length();
  int LenY = y.length();
  int o = max(LenX, LenY); //取长串的长度
  //若小于一定值，则直接相乘
  if (o <= 4)
    return Tostring(Stoi(x) * Stoi(y));

  if (o & 1)
    o++;

  int lenX = x.length();
  int lenY = y.length();
  for (lenY; lenY < o; lenY++)
    y = "0" + y;

  for (lenX; lenX < o; lenX++)
    x = "0" + x;

  int n = o / 2;

  string AC = D_ADD(x.substr(0, n), y.substr(0, n));
  string BD = D_ADD(x.substr(n, n), y.substr(n, n));
  string AD = D_ADD(x.substr(0, n), y.substr(n, n));
  string BC = D_ADD(x.substr(n, n), y.substr(0, n));

  string AD_BC = BigNumberAccumulate(AD, BC);

  AD_BC.resize(AD_BC.length() + n, '0');
  AC.resize(AC.length() + o, '0');


  string XY = BigNumberAccumulate(AC, BigNumberAccumulate(AD_BC, BD));
  return XY;
}

int main()
{
  string x;
  int y;

  //string z;
  while (cin >> x >> y)
  {

    //去除多余 0
    int posX = x.find('.');

    if (posX != -1)
    {
      while (x[x.length() - 1] == '0')
        x = x.substr(0, x.length() - 1);
                if(x[x.length() - 1] == '.')
         x = x.substr(0, x.length() - 1);
    
    //去除小数点
    x = Pointclear(x, posX);

    string sum = x;

    for (int i = 0; i < y - 1; i++)
    {
      string temp =  D_ADD(sum, x);
      sum = temp;
    }

    int len = x.length();
    int lenSum = sum.length();

    if ((len - posX) * y <= lenSum) //当小数点后面的位数等于结果
    {
      if (posX != -1)
      {
        int h = (lenSum - (len - posX) * y);
        sum.insert(h, ".");
      }
    }
    else
    {
      for (int i = lenSum; i < (len - 1) * y; i++)
        sum = "0" + sum;
      sum = "." + sum;
    }

    //去除多余 0
   
      while ( sum[ sum.length() - 1] == '0')
        sum =  sum.substr(0,  sum.length() - 1);
                if( sum[ sum.length() - 1] == '.')
          sum =  sum.substr(0,  sum.length() - 1);
    cout << sum << endl;
  }
}