//設計一個支持大數運算的計算器，其中乘法使用分治法求解。該計算器支持加減乘除還有開方根運算。

#include <iostream>
#include <list>
#include <string>
#include <cstdio>
#include <cctype>
#include <cmath>
using namespace std;

list<char> Add(list<char> s, list<char> t);
list<char> Sub(list<char> s, list<char> t);
list<char> Mul(list<char> s, list<char> t);
void Div(list<char> s, list<char> t);
void  Root(list<char>);
void print(list<char> ans);

void printhelp()             //打印幫助信息
{
    cout << "請選擇要進行的大數運算" << endl;
    cout << "1:加法運算" << endl;
    cout << "2:減法運算" << endl;
    cout << "3:乘法運算" << endl;
    cout << "4:除法運算" << endl;
    cout << "5:開平方根運算" << endl;
    cout << "6:退出" << endl;
}
list<char> Add(list<char> num1,list<char> num2)  //加法運算
{
    list<char> ans;
    list<char>::iterator iter1,iter2;
    iter1 = num1.begin();
    iter2 = num2.begin();
    int sign = 0;                                   //標記結果符號
    if((*iter1) == '-' && (*iter2) == '-')        //如果兩個數都是負數
    {
        num1.pop_front();
        num2.pop_front();
        sign = 1;
        ans = Add(num1,num2);
        ans.push_front('-');
    }
    else if((*iter1) == '-' && (*iter2) != '-')      //如果一負一正
    {
        num1.pop_front();
        ans = Sub(num2,num1);
        
    }
    else if((*iter1) != '-' && (*iter2) == '-')      //如果一正一負
    {
        num2.pop_front();
        ans = Sub(num1,num2);
    }
    else                                          //如果都為正
    {
        int len1,len2,i,len,carry;
        len1 = num1.size();
        len2 = num2.size();
        if(len1 >= len2)                     //補齊兩個數的位數
        {
            len = len1;
            for(i = 0; i < len1 - len2; i++)
                num2.push_front('0');
        }
        else
        {
            len = len2;
            for(i = 0; i < len2 - len1; i++)
                num1.push_front('0');
        }
        //print(num1);
        //print(num2);
        carry = 0;
        iter1 = num1.end();
        iter2 = num2.end();
        iter1--;
        iter2--;
        for(;(iter1 != num1.begin()) && (iter2 != num2.begin()); --iter1,--iter2)  //進行運算
        {
            i = (*iter1 - '0') + (*iter2 - '0') + carry;
            //cout << (*iter1 - '0') << " " << (*iter2 - '0') << " " << i << endl;
            ans.push_front((i % 10) + '0');
            carry = i / 10;
        }
        i = (*iter1 - '0') + (*iter2 - '0') + carry;
        //cout << (*iter1 - '0') << " " << (*iter2 - '0') << " " << i << endl;
        ans.push_front((i % 10) + '0');
        carry = i / 10;
        if(carry)
            ans.push_front(carry+'0');
    }
    return ans;                                                     //返回結果

}
list<char> Sub(list<char> num1,list<char> num2)                    //減法運算
{
    list<char> ans;
    int sign = 0;
    list<char>::iterator iter1,iter2;
    int len1,len2,len;
    iter1 = num1.begin();
    iter2 = num2.begin();
    if((*iter1) == '-' && (*iter2) == '-')                  //如果兩個數都為負數
    {
        num2.pop_front();
        num1.pop_front();
        ans = Sub(num2,num1);
        //ans.push_front('-');
    }
    else if( (*iter1) == '-' && (*iter2) != '-')              //如果一負一正
    {
        num1.pop_front();
        ans = Add(num1,num2);
        ans.push_front('-');
    }
    else if( (*iter1) != '-' && (*iter2) == '-')              //如果一正一負
    {
        num2.pop_front();
        ans = Add(num1,num2);
        
    }
    else                                                   //如果都為正
    {
        len1 = num1.size();
        len2 = num2.size();
        if(len1 >= len2)                                 //補齊位數
        {
            len = len1;
            for(int i = 0; i < len1 - len2; i++)
                num2.push_front('0');
        }
        else
        {
            len = len2;
            for(int i = 0; i < len2 - len1; i++)
                num1.push_front('0');
        }
        //print(num1);cout << endl;
        //print(num2);cout << endl;
        int carry = 0,i;
        iter1 = num1.end();
        iter2 = num2.end();
        iter1--;
        iter2--;
        for(;(iter1 != num1.begin()) && (iter2 != num2.begin()); --iter1,--iter2)    //進行運算
        {
            i = (*iter1 - '0' - carry) - (*iter2 - '0');
            carry = 0;
            if( i < 0)
            {
                i += 10;
                carry = 1;
            }
            //cout << (*iter1 - '0') << " " << (*iter2 - '0') << " " << i << endl;
            ans.push_front((i % 10) + '0');
        }
        i = (*iter1 - '0' - carry) - (*iter2 - '0');
        if(i < 0)
        {
            i += 10;
            sign = 1;
        }
        //cout << (*iter1 - '0') << " " << (*iter2 - '0') << " " << i << endl;
        if(i) ans.push_front(i + '0');
        if(sign)
            ans.push_front('-');
    }
    return ans;

}
list<char> Mul(list<char> num1,list<char> num2)  // 分治法求兩大數的積
{
    list<char> ans;
    int sign = 0;
    int len1,len2,len;
    list<char>::iterator iter1,iter2,iter;
    list<char> high,low;
    list<char> anshigh,anslow;
    int th,tl;
    int i,j,k;
    //print(num1);cout << endl;
    //print(num2);cout << endl;
    if(num1.size() == 1 && num2.size() == 1)     //如果兩數都已是一位數，則進行運算
    {
        th = *(num1.begin()) - '0';
        tl = *(num2.begin()) - '0';
        th *= tl;
        ans.push_front( th % 10 + '0');
        ans.push_front( th / 10 + '0');
        return ans;
    }
    else if(num1.size() == 1 && num2.size() > 1)            //如果num1位數大于1，則對Num1分治求積
    {
         if(*(num2.begin()) == '-')
           {
                sign = 1;
                num2.pop_front();
           }
         len2 = num2.size();
         if(len2 == 1)
         {
            ans = Mul(num1,num2);
            if(sign)
                ans.push_front('-');
         }
         else
         {
            for(iter= num2.begin(),i = 0; i < len2 / 2; i++,iter++)
            {
                high.push_back(*iter);
            }
            for(;iter!=num2.end();iter++)
            {
                low.push_back(*iter);
            }
            len = low.size();
            anshigh = Mul(num1,high);                 //num1分為兩部分，high,low
            anslow = Mul(num1,low);
            for(i = 0; i < len; i++)
                anshigh.push_back('0');
            ans = Add(anshigh,anslow);                 //合并結果
            if(sign)
                ans.push_front('-');
         }
         return ans;
    }
    else if(num2.size() == 1 && num1.size() > 1)              //如果num2位數大于1，則對Num2分治求積
    {
         if(*(num1.begin()) == '-')
           {
                sign = 1;
                num1.pop_front();
           }
         len1 = num1.size();
         if(len2 == 1)
         {
            ans = Mul(num1,num2);
            if(sign)
                ans.push_front('-');
         }
         else
         {
            for(iter= num1.begin(),i = 0; i < len1 / 2; i++,iter++)
            {
                high.push_back(*iter);
            }
            for(;iter!=num1.end();iter++)
            {
                low.push_back(*iter);
            }
            len = low.size();
            anshigh = Mul(num2,high);                   //num2分為兩部分，high,low
            anslow = Mul(num2,low);
            for(i = 0; i < len; i++)
                anshigh.push_back('0');
            ans = Add(anshigh,anslow);                    //合并結果
            if(sign)
                ans.push_front('-');
         }
         return ans;
    }                                                       //如果兩數位數都大于1，則都運用分治
    else
    {
        list<char> num1high,num1low,num2high,num2low;
        int flag1 = 0,flag2 = 0;
        if(*(num1.begin()) == '-')
        {
            flag1 = 1;
            num1.pop_front();
        }
        if(*(num2.begin()) == '-')
        {
            flag2 = 1;
            num2.pop_front();
        }
        if((flag1 == 1 && flag2 == 0)||(flag1 == 0 && flag2 == 1))  //如果有一正一負，則標記結果為負
        {
            sign = 1;
        }
        len1 = num1.size();
        len2 = num2.size();
        if(len1 == 1 || len2 == 1)                 //如果有一個數是一位數，則直接遞歸調用
        {
            ans = Mul(num1,num2);
            if(sign)
                ans.push_front('-');
        }
        else
        {                                                //否則分治法求
            for(iter = num1.begin(),i = 0; i < len1 / 2; iter++,i++)
                num1high.push_back(*iter);            //被乘數高位部分
            for( ; iter != num1.end(); iter++)
                num1low.push_back(*iter);                 //被乘數低位部分
            for(iter = num2.begin(),i = 0; i < len2 / 2; iter++,i++)
                num2high.push_back(*iter);                  //乘數高位部分
            for( ; iter != num2.end(); iter++)
                num2low.push_back(*iter);                    //乘數低位部分
            int a = (len1 + 1) / 2;
            int b = (len2 + 1) / 2;
            list<char> AC,AD,BC,BD;
            //print(num2high);cout << endl;
            //print(num2low);cout << endl;
            AC = Mul(num1high,num2high);                  //運用X=A*10^a + B; Y= C*10^b + D;
            AD = Mul(num1high,num2low);                   // X*Y = AC * 10 ^(a+b) + AD *10^a + BC * 10 ^b + BD公式求
            BC = Mul(num1low,num2high);
            BD = Mul(num1low,num2low);
            for(i = 0; i < a + b; i++)
                AC.push_back('0');
            for(i = 0; i < a; i++)
                AD.push_back('0');
            for(i = 0; i < b; i++)
                BC.push_back('0');
            ans = Add(AC,AD);
            ans = Add(ans,BC);
            ans = Add(ans,BD);                            //累加結果
            if(sign)
                ans.push_front('-');
        }
        return ans;

    }

}
void Div(list<char> num1,list<char> num2)                 //用輾轉相除求結果
{
    list<char> ans;
    list<char> temp;
    int len1,len2,len;
    int i,j,k;
    int sign = 0;
    int flag1 = 0,flag2 = 0;
    list<char>::iterator iter;
    if(*(num1.begin()) == '-')
    {
        flag1 = 1;
        num1.pop_front();
    }
    if(*(num2.begin()) == '-')
    {
        flag2 = 1;
        num2.pop_front();
    }
    if((flag1 == 1 && flag2 != 1) || (flag1 == 0 && flag2 == 1))
        sign = 1;                                          //標記結果符號
    len1 = num1.size();
    len2 = num2.size();
    if(len1 < len2)                                 //如果被除數小于除法，除數為0
    {
        cout << "商是0；余數是" ;
        print(num2);