模板2 (Past)

#include "pch.h"
#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>
#include <functional>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <string.h>
using namespace std;
const long double PI = 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446;


//****************************模板BEGIN***********************************
class StringUtil {
public:
    //用c来分割s，返回分割后的一个个字符串
    vector<string> split(string s, char c);
    //去除一个字符串前后的空格
    string trim(string s);
    //把一个字符串转换为字符vector
    vector<char> toCharVector(string s);
    //把一个字符vector转换为字符串
    string vectorToString(vector<char> v);
    //专门用来分割空格
    vector<string> splitBlank(string s);
};

class BigNumUtil {
public:
    //两个超大正整数的加法
    string bigDecimalAdd(string num1, string num2);
    //两个超大正整数的乘法
    string bigDecimalMultiply(string num1, string num2);
    //两个超大正整数的减法，注意需要num1≥num2
    string bigDecimalMinus(string num1, string num2);
    //两个超大正整数的除法，小数部分为零的话就不会显示，如果除不尽，cir_start和cir_end指出了循环节的首尾（小数点后第x位到小数点后第y位）
    string bigDecimalDivide(string up, string down, int& cir_start, int& cir_end);
    //超大正整数的Cnm
    string bigDecimalCnm(int n, int m);
    //两个超大正整数比较大小
    int bigDecimalCompare(string num1, string num2);
};

class MathUtil {
public:
    //最大公约数
    int getLCM(int a, int b);
    //最小公倍数
    int getGCD(int a, int b);
    //计算kBase^kExp
    unsigned long long pow(unsigned long long const kBase, unsigned long long const kExp);
    //计算Cnm
    unsigned long long combine(int n, int m);
    //大数情况，计算kBase^kExp再对kMod取余后的结果
    unsigned long long powAndMod(unsigned long long const kBase, unsigned long long const kExp, unsigned long long const kMod);
    //大数情况，下面三个函数都是为了计算 Cnm%mod 的，用第三个就行
    unsigned long long exp_mod(unsigned long long a, unsigned long long b, unsigned long long p);
    unsigned long long Comb(unsigned long long a, unsigned long long b, unsigned long long p);
    unsigned long long combineAndMod(unsigned long long n, unsigned long long m, unsigned long long mod);
};

//专门用来求解二项式(ax+by)^k中x^n*y^m的系数，通式为Ckn*a^n*b^m
class PolynomialUtil {
public:
    //重点就在于把阶乘打表
    vector<unsigned long long> factorial;
    //这个构造方法最多使用一次，因为打表很花时间
    //maxK指的是k的最大值，mod是指结果对多少取余，这两个参数题目一般都会给出，如果maxK不给那就取一个较大的值
    PolynomialUtil(int maxK, unsigned long long mod);
    unsigned long long go(unsigned long long a, unsigned long long b, unsigned long long k, unsigned long long n, unsigned long long m, unsigned long long mod);
};

//初始化一个m*n的二维数组，使用dtf填充，返回的vector可以当作数组一样使用
template<typename T>
vector<vector<T>> initMatrix(int m, int n, T dft);


//****************************模板END*************************************

int main() {
    int T;
    cin >> T;
    for (int t = 0;t < T;t++) {

        cout << "case #" << t << ":" << endl;

    }
}









//****************************模板BEGIN***********************************
vector<string> StringUtil::split(string s, char c) {
    vector<string> result;
    int len = s.size();
    string temp = "";
    for (int i = 0;i < len;i++) {
        if (s[i] != c) {
            temp += s[i];
        }
        else {
            result.push_back(temp);
            temp = "";
        }
    }
    if (temp != "") {
        result.push_back(temp);
    }
    return result;
}
string StringUtil::trim(string s) {
    string res = "";
    int ptr = 0;
    while (s[ptr] == ' ') {
        ptr++;
    }
    while (ptr != s.size()) {
        res += s[ptr++];
    }
    auto it = res.end() - 1;
    while (*it == ' ') {
        res.erase(it);
        it--;
    }
    return res;
}
vector<char> StringUtil::toCharVector(string s) {
    vector<char> res;
    for (int i = 0;i < s.size();i++) {
        res.push_back(s[i]);
    }
    return res;
}
string StringUtil::vectorToString(vector<char> v) {
    string res = "";
    for (char c : v) {
        res += c;
    }
    return res;
}
vector<string> StringUtil::splitBlank(string s) {
    vector<string> result;
    s = StringUtil().trim(s);
    int ptr = 0;
    bool processChar = true;
    string temp = "";
    while (true) {
        if (processChar) {
            if (s[ptr] != ' ') {
                temp += s[ptr];
                ptr++;
            }
            else {
                result.push_back(temp);
                temp = "";
                processChar = false;
            }
        }
        else {
            if (s[ptr] != ' ') {
                temp += s[ptr];
                processChar = true;
            }
            ptr++;
        }
        if (ptr == s.size()) {
            if (temp != "") {
                result.push_back(temp);
            }
            break;
        }
    }
    return result;
}
string BigNumUtil::bigDecimalAdd(string num1, string num2) {
    string s = num2;
    string l = num1;
    if (num1.size() <= num2.size()) {
        s = num1;
        l = num2;
    }
    int ssize = s.size();
    int lsize = l.size();
    int sptr = ssize - 1;
    int lptr = lsize - 1;
    vector<int> v;
    int up = 0;
    while (true) {
        int digit1 = s[sptr--] - '0';
        int digit2 = l[lptr--] - '0';
        int cal = digit1 + digit2 + up;
        if (cal >= 10) {
            up = 1;
            cal -= 10;
        }
        else {
            up = 0;
        }
        v.push_back(cal);
        if (sptr == -1) {
            while (lptr != -1) {
                cal = l[lptr--] - '0' + up;
                if (cal >= 10) {
                    up = 1;
                    cal -= 10;
                }
                else {
                    up = 0;
                }
                v.push_back(cal);
            }
            if (up == 1) {
                v.push_back(1);
            }
            break;
        }
    }
    string res = "";
    for (int i = v.size() - 1;i >= 0;i--) {
        res += (v[i] + '0');
    }
    return res;
}
string BigNumUtil::bigDecimalMultiply(string num1, string num2) {
    string s = num2;
    string l = num1;
    if (num1.size() <= num2.size()) {
        s = num1;
        l = num2;
    }
    int ssize = s.size();
    int lsize = l.size();
    vector<string> numList;
    for (int i = ssize - 1;i >= 0;i--) {
        stack<char> temp;
        int digit1 = s[i] - '0';
        int up = 0;
        for (int j = lsize - 1;j >= 0;j--) {
            int digit2 = l[j] - '0';
            int cal = digit1 * digit2 + up;
            if (cal >= 10) {
                up = cal / 10;
                cal = cal % 10;
            }
            else {
                up = 0;
            }
            temp.push(cal + '0');
            if (j == 0 && up != 0) {
                temp.push(up + '0');
            }
        }
        string res = "";
        while (!temp.empty()) {
            res += temp.top();
            temp.pop();
        }
        //补上0，比如40*123时，那个0得在这里补上
        for (int j = 0;j < ssize - 1 - i;j++) {
            res += "0";
        }
        numList.push_back(res);
    }
    string res = "0";
    for (int i = 0;i < numList.size();i++) {
        res = BigNumUtil::bigDecimalAdd(res, numList[i]);
    }
    return res;
}
string BigNumUtil::bigDecimalMinus(string num1, string num2) {
    if (num1 == num2) {
        return "0";
    }
    int size1 = num1.size();
    int size2 = num2.size();
    int ptr1 = size1 - 1;
    int ptr2 = size2 - 1;
    int borrow = 0;
    stack<char> stk;
    while (true) {
        int cal = num1[ptr1--] - '0' - (num2[ptr2--] - '0') - borrow;
        if (cal < 0) {
            borrow = 1;
            cal += 10;
        }
        else {
            borrow = 0;
        }
        stk.push(cal + '0');
        if (ptr2 == -1) {
            while (ptr1 != -1) {
                int cal = num1[ptr1--] - '0' - borrow;
                if (cal < 0) {
                    borrow = 1;
                    cal += 10;
                }
                else {
                    borrow = 0;
                }
                stk.push(cal + '0');
            }
            while (stk.top() == '0') {
                stk.pop();
            }
            break;
        }
    }
    string res = "";
    while (!stk.empty()) {
        res += stk.top();
        stk.pop();
    }
    return res;
}
string BigNumUtil::bigDecimalDivide(string up, string down, int& cir_start, int& cir_end) {

    if (up == "0") {
        return "0";
    }

    if (up == down) {
        return "1";
    }

    //准备好分母的所有倍数，后续可以直接取用
    vector<string> timesOfDown;
    timesOfDown.push_back("0");
    timesOfDown.push_back(down);
    for (int i = 2;i <= 10;i++) {
        timesOfDown.push_back(bigDecimalMultiply(string(1, i + '0'), down));
    }

    int ptr = 0;
    int upSize = up.size();

    //被减数
    string currentString = "";

    string intPart = "";

    //处理整数部分
    if (bigDecimalCompare(up, down) == 1) {

        while (true) {

            if (ptr < upSize) {
                currentString += up[ptr];
            }
            else if (ptr == upSize) {
                //如果currentString不为""，说明整数部分除不尽，还有小数部分，现在的这个currentString就是后续处理小数部分时的分子
                up = currentString;
                break;
            }
            ptr++;
            for (int i = 1;i < 11;i++) {
                if (bigDecimalCompare(timesOfDown[i], currentString) == 1) {
                    //减数
                    string minu = timesOfDown[i - 1];
                    //商
                    intPart += (i - 1 + '0');
                    //作差
                    currentString = bigDecimalMinus(currentString, minu);
                    //余数为0，说明除尽了
                    if (currentString == "0") {
                        currentString = "";

                    }
                    break;
                }
            }

        }
        //去除前导0
        auto it = intPart.begin();
        while (*it == '0') {
            intPart.erase(it);
        }
    }


    if (up == "") {
        return intPart;
    }
    else {
        if (intPart == "") {
            intPart = "0";
        }
        //被减数
        currentString = up;

        string floatPart = "";

        //记录已经出现过的余数和第一次出现的位置（小数点后x位）
        unordered_map<string, int> left;
        int index = 0;

        while (true) {
            bool canStop = false;
            index++;
            for (int i = 1;i < 11;i++) {
                if (bigDecimalCompare(timesOfDown[i], currentString) == 1) {
                    //减数
                    string minu = timesOfDown[i - 1];
                    //商
                    floatPart += (i - 1 + '0');
                    if (index == 1) {
                        floatPart += ".";
                    }
                    //作差
                    currentString = bigDecimalMinus(currentString, minu);
                    //如果是第一次出现的余数，加入到set中
                    if (left.find(currentString) == left.end()) {
                        left.insert(make_pair(currentString, index));
                    }
                    //否则，说明出现了循环节
                    else {
                        cir_start = left[currentString];
                        cir_end = index - 1;
                        canStop = true;
                    }
                    //余数为0，说明除尽了
                    if (currentString == "0") {
                        canStop = true;
                    }
                    currentString += "0";
                    break;
                }
            }
            if (canStop) {
                break;
            }
        }
        return intPart + floatPart.substr(1);

    }

}
int BigNumUtil::bigDecimalCompare(string num1, string num2) {
    if (num1.size() > num2.size()) {
        return 1;
    }
    if (num1.size() < num2.size()) {
        return -1;
    }
    int ptr = 0;
    while (ptr != num1.size()) {
        if (num1[ptr] > num2[ptr]) {
            return 1;
        }
        if (num1[ptr] < num2[ptr]) {
            return -1;
        }
        ptr++;
    }
    return 0;

}
template<typename T>
vector<vector<T>> initMatrix(int m, int n, T dft) {
    vector<vector<T>> matrix;
    vector<T> row;
    row.resize(n, dft);
    matrix.resize(m, row);
    return matrix;
}
int MathUtil::getLCM(int a, int b) {
    int max = (a > b ? a : b);
    int min = (a < b ? a : b);
    int res = max % min;
    while (res) {
        max = min;
        min = res;
        res = max % min;
    }
    return min;
}
int MathUtil::getGCD(int a, int b) {
    return a * b / getLCM(a, b);
}
unsigned long long MathUtil::powAndMod(unsigned long long const kBase, unsigned long long const kExp, unsigned long long const kMod) {
    unsigned long long ret = 1;
    for (unsigned long long i = kExp, base = kBase % kMod; i; i >>= 1) {
        if (i & 1) {
            ret = ret * base % kMod;
        }
        base = base * base % kMod;
    }
    return ret;
}
unsigned long long MathUtil::pow(unsigned long long const kBase, unsigned long long const kExp) {
    unsigned long long ret = 1;
    for (unsigned long long i = kExp, base = kBase; i; i >>= 1) {
        if (i & 1) {
            ret = ret * base;
        }
        base = base * base;
    }
    return ret;
}
unsigned long long MathUtil::exp_mod(unsigned long long a, unsigned long long b, unsigned long long p) {
    long long res = 1;
    while (b != 0) {
        if (b & 1) res = (res * a) % p;
        a = (a*a) % p;
        b >>= 1;
    }
    return res;
}
unsigned long long MathUtil::Comb(unsigned long long a, unsigned long long b, unsigned long long p) {
    if (a < b) return 0;
    if (a == b) return 1;
    if (b > a - b) b = a - b;

    unsigned long long ans = 1, ca = 1, cb = 1;
    for (unsigned long long i = 0; i < b; ++i) {
        ca = (ca * (a - i)) % p;
        cb = (cb * (b - i)) % p;
    }
    ans = (ca*exp_mod(cb, p - 2, p)) % p;
    return ans;
}
unsigned long long MathUtil::combineAndMod(unsigned long long n, unsigned long long m, unsigned long long mod) {
    unsigned long long ans = 1;

    while (n&&m&&ans) {
        ans = (ans*Comb(n%mod, m%mod, mod)) % mod;
        n /= mod;
        m /= mod;
    }
    return ans;
}
unsigned long long MathUtil::combine(int n, int m) {
    if (m < n - m) m = n - m;
    unsigned long long ans = 1;
    for (int i = m + 1; i <= n; i++) ans *= i;
    for (int i = 1; i <= n - m; i++) ans /= i;
    return ans;
}
PolynomialUtil::PolynomialUtil(int maxK, unsigned long long mod) {
    factorial.resize(maxK + 1);
    factorial[0] = 1;
    for (int i = 1; i < maxK + 1; ++i) {
        factorial[i] = factorial[i - 1] * i % mod;
    }
}
unsigned long long PolynomialUtil::go(unsigned long long a, unsigned long long b, unsigned long long k, unsigned long long n, unsigned long long m, unsigned long long mod) {
    unsigned long long inv_binom = MathUtil().powAndMod(factorial[n] * factorial[m] % mod, mod - 2, mod);
    unsigned long long apow = MathUtil().powAndMod(a, n, mod);
    unsigned long long bpow = MathUtil().powAndMod(b, m, mod);
    unsigned long long ans = factorial[k] * inv_binom % mod;
    ans = ans * apow % mod;
    ans = ans * bpow % mod;
    return ans;
}
string BigNumUtil::bigDecimalCnm(int n, int m) {
    string up = "1";
    for (int i = 0;i < m;i++) {
        up = BigNumUtil().bigDecimalMultiply(up, to_string(n - i));
    }
    string down = "1";
    for (int i = 2;i <= m;i++) {
        down = BigNumUtil().bigDecimalMultiply(down, to_string(i));
    }
    int useless;
    return BigNumUtil().bigDecimalDivide(up, down, useless, useless);
}
//****************************模板END*************************************

#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>
#include <functional>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <string.h>
using namespace std;
using u64 = uint64_t;
const long double PI = 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446;


//****************************模板BEGIN***********************************
class StringUtil {
public:
    //用c来分割s，返回分割后的一个个字符串
    vector<string> split(string s, char c);
    //去除一个字符串前后的空格
    string trim(string s);
    //把一个字符串转换为字符vector
    vector<char> toCharVector(string s);
    //把一个字符vector转换为字符串
    string vectorToString(vector<char> v);
    //专门用来分割空格
    vector<string> splitBlank(string s);
};

class BigNumUtil {
public:
    //两个超大正整数的加法
    string bigDecimalAdd(string num1, string num2);
    //两个超大正整数的乘法
    string bigDecimalMultiply(string num1, string num2);
    //两个超大正整数的减法，注意需要num1≥num2
    string bigDecimalMinus(string num1, string num2);
    //两个超大正整数的除法，小数部分为零的话就不会显示，如果除不尽，cir_start和cir_end指出了循环节的首尾（小数点后第x位到小数点后第y位）
    string bigDecimalDivide(string up, string down, int& cir_start, int& cir_end);
    //超大正整数的Cnm（n是大的）
    string bigDecimalCnm(int n, int m);
    //两个超大正整数比较大小，num1大的话返回1，相同返回0，num1小的话返回-1
    int bigDecimalCompare(string num1, string num2);
    //把一个小数转换为分数，如果是无限循环小数，循环节需要用[]包起来，返回分数的分子和分母，分别存在up和down中
    void floatToFraction(string floatString, long long& up, long long& down);
    //把一个数转换为科学计数法，num是正数，p为有效位的位数（不包括小数点）
    //返回形式为aFb，超出p的话a会四舍五入，不足p的位数用0补
    void numToSci(string num, int p, string& a, string& b);
};

class MathUtil {
public:
    //最大（G）公约数
    long long getGCD(long long a, long long b);
    //最小（L）公倍数
    long long getLCM(long long a, long long b);
    //计算kBase^kExp
    unsigned long long pow(unsigned long long const kBase, unsigned long long const kExp);
    //计算Cnm
    unsigned long long combine(int n, int m);
    //大数情况，计算kBase^kExp再对kMod取余后的结果
    unsigned long long powAndMod(unsigned long long const kBase, unsigned long long const kExp, unsigned long long const kMod);
    //大数情况，下面三个函数都是为了计算 Cnm%mod 的，用第三个就行
    unsigned long long exp_mod(unsigned long long a, unsigned long long b, unsigned long long p);
    unsigned long long Comb(unsigned long long a, unsigned long long b, unsigned long long p);
    unsigned long long combineAndMod(unsigned long long n, unsigned long long m, unsigned long long mod);
};

//专门用来求解二项式(ax+by)^k中x^n*y^m的系数，通式为Ckn*a^n*b^m
class PolynomialUtil {
public:
    //重点就在于把阶乘打表
    vector<unsigned long long> factorial;
    //这个构造方法最多使用一次，因为打表很花时间
    //maxK指的是k的最大值，mod是指结果对多少取余，这两个参数题目一般都会给出，如果maxK不给那就取一个较大的值
    PolynomialUtil(int maxK, unsigned long long mod);
    unsigned long long go(unsigned long long a, unsigned long long b, unsigned long long k, unsigned long long n, unsigned long long m, unsigned long long mod);
};

//初始化一个m*n的二维数组，使用dft填充，返回的vector可以当作数组一样使用
template<typename T>
vector<vector<T>> initMatrix(int m, int n, T dft);


//****************************模板END*************************************


int cal(int total) {
    int count = 0;
    while (total >= 100) {
        total -= 100;
        count++;
    }
    while (total >= 50) {
        total -= 50;
        count++;
    }
    while (total >= 20) {
        total -= 20;
        count++;
    }
    while (total >= 10) {
        total -= 10;
        count++;
    }
    while (total >= 5) {
        total -= 5;
        count++;
    }
    count += total;
    return count;
}

int main() {

}


//****************************模板BEGIN***********************************
vector<string> StringUtil::split(string s, char c) {
    vector<string> result;
    int len = s.size();
    string temp = "";
    for (int i = 0;i < len;i++) {
        if (s[i] != c) {
            temp += s[i];
        }
        else {
            result.push_back(temp);
            temp = "";
        }
    }
    if (temp != "") {
        result.push_back(temp);
    }
    return result;
}
string StringUtil::trim(string s) {
    string res = "";
    int ptr = 0;
    while (s[ptr] == ' ') {
        ptr++;
    }
    while (ptr != s.size()) {
        res += s[ptr++];
    }
    auto it = res.end() - 1;
    while (*it == ' ') {
        res.erase(it);
        it--;
    }
    return res;
}
vector<char> StringUtil::toCharVector(string s) {
    vector<char> res;
    for (int i = 0;i < s.size();i++) {
        res.push_back(s[i]);
    }
    return res;
}
string StringUtil::vectorToString(vector<char> v) {
    string res = "";
    for (char c : v) {
        res += c;
    }
    return res;
}
vector<string> StringUtil::splitBlank(string s) {
    vector<string> result;
    s = StringUtil().trim(s);
    int ptr = 0;
    bool processChar = true;
    string temp = "";
    while (true) {
        if (processChar) {
            if (s[ptr] != ' ') {
                temp += s[ptr];
                ptr++;
            }
            else {
                result.push_back(temp);
                temp = "";
                processChar = false;
            }
        }
        else {
            if (s[ptr] != ' ') {
                temp += s[ptr];
                processChar = true;
            }
            ptr++;
        }
        if (ptr == s.size()) {
            if (temp != "") {
                result.push_back(temp);
            }
            break;
        }
    }
    return result;
}
string BigNumUtil::bigDecimalAdd(string num1, string num2) {
    string s = num2;
    string l = num1;
    if (num1.size() <= num2.size()) {
        s = num1;
        l = num2;
    }
    int ssize = s.size();
    int lsize = l.size();
    int sptr = ssize - 1;
    int lptr = lsize - 1;
    vector<int> v;
    int up = 0;
    while (true) {
        int digit1 = s[sptr--] - '0';
        int digit2 = l[lptr--] - '0';
        int cal = digit1 + digit2 + up;
        if (cal >= 10) {
            up = 1;
            cal -= 10;
        }
        else {
            up = 0;
        }
        v.push_back(cal);
        if (sptr == -1) {
            while (lptr != -1) {
                cal = l[lptr--] - '0' + up;
                if (cal >= 10) {
                    up = 1;
                    cal -= 10;
                }
                else {
                    up = 0;
                }
                v.push_back(cal);
            }
            if (up == 1) {
                v.push_back(1);
            }
            break;
        }
    }
    string res = "";
    for (int i = v.size() - 1;i >= 0;i--) {
        res += (v[i] + '0');
    }
    return res;
}
string BigNumUtil::bigDecimalMultiply(string num1, string num2) {
    string s = num2;
    string l = num1;
    if (num1.size() <= num2.size()) {
        s = num1;
        l = num2;
    }
    int ssize = s.size();
    int lsize = l.size();
    vector<string> numList;
    for (int i = ssize - 1;i >= 0;i--) {
        stack<char> temp;
        int digit1 = s[i] - '0';
        int up = 0;
        for (int j = lsize - 1;j >= 0;j--) {
            int digit2 = l[j] - '0';
            int cal = digit1 * digit2 + up;
            if (cal >= 10) {
                up = cal / 10;
                cal = cal % 10;
            }
            else {
                up = 0;
            }
            temp.push(cal + '0');
            if (j == 0 && up != 0) {
                temp.push(up + '0');
            }
        }
        string res = "";
        while (!temp.empty()) {
            res += temp.top();
            temp.pop();
        }
        //补上0，比如40*123时，那个0得在这里补上
        for (int j = 0;j < ssize - 1 - i;j++) {
            res += "0";
        }
        numList.push_back(res);
    }
    string res = "0";
    for (int i = 0;i < numList.size();i++) {
        res = BigNumUtil::bigDecimalAdd(res, numList[i]);
    }
    return res;
}
string BigNumUtil::bigDecimalMinus(string num1, string num2) {
    if (num1 == num2) {
        return "0";
    }
    int size1 = num1.size();
    int size2 = num2.size();
    int ptr1 = size1 - 1;
    int ptr2 = size2 - 1;
    int borrow = 0;
    stack<char> stk;
    while (true) {
        int cal = num1[ptr1--] - '0' - (num2[ptr2--] - '0') - borrow;
        if (cal < 0) {
            borrow = 1;
            cal += 10;
        }
        else {
            borrow = 0;
        }
        stk.push(cal + '0');
        if (ptr2 == -1) {
            while (ptr1 != -1) {
                int cal = num1[ptr1--] - '0' - borrow;
                if (cal < 0) {
                    borrow = 1;
                    cal += 10;
                }
                else {
                    borrow = 0;
                }
                stk.push(cal + '0');
            }
            while (stk.top() == '0') {
                stk.pop();
            }
            break;
        }
    }
    string res = "";
    while (!stk.empty()) {
        res += stk.top();
        stk.pop();
    }
    return res;
}
string BigNumUtil::bigDecimalDivide(string up, string down, int& cir_start, int& cir_end) {

    if (up == "0") {
        return "0";
    }

    if (up == down) {
        return "1";
    }

    //准备好分母的所有倍数，后续可以直接取用
    vector<string> timesOfDown;
    timesOfDown.push_back("0");
    timesOfDown.push_back(down);
    for (int i = 2;i <= 10;i++) {
        timesOfDown.push_back(bigDecimalMultiply(string(1, i + '0'), down));
    }

    int ptr = 0;
    int upSize = up.size();

    //被减数
    string currentString = "";

    string intPart = "";

    //处理整数部分
    if (bigDecimalCompare(up, down) == 1) {

        while (true) {

            if (ptr < upSize) {
                currentString += up[ptr];
            }
            else if (ptr == upSize) {
                //如果currentString不为""，说明整数部分除不尽，还有小数部分，现在的这个currentString就是后续处理小数部分时的分子
                up = currentString;
                break;
            }
            ptr++;
            for (int i = 1;i < 11;i++) {
                if (bigDecimalCompare(timesOfDown[i], currentString) == 1) {
                    //减数
                    string minu = timesOfDown[i - 1];
                    //商
                    intPart += (i - 1 + '0');
                    //作差
                    currentString = bigDecimalMinus(currentString, minu);
                    //余数为0，说明除尽了
                    if (currentString == "0") {
                        currentString = "";

                    }
                    break;
                }
            }

        }
        //去除前导0
        auto it = intPart.begin();
        while (*it == '0') {
            intPart.erase(it);
        }
    }


    if (up == "") {
        return intPart;
    }
    else {
        if (intPart == "") {
            intPart = "0";
        }
        //被减数
        currentString = up;

        string floatPart = "";

        //记录已经出现过的余数和第一次出现的位置（小数点后x位）
        unordered_map<string, int> left;
        int index = 0;

        while (true) {
            bool canStop = false;
            index++;
            for (int i = 1;i < 11;i++) {
                if (bigDecimalCompare(timesOfDown[i], currentString) == 1) {
                    //减数
                    string minu = timesOfDown[i - 1];
                    //商
                    floatPart += (i - 1 + '0');
                    if (index == 1) {
                        floatPart += ".";
                    }
                    //作差
                    currentString = bigDecimalMinus(currentString, minu);
                    //如果是第一次出现的余数，加入到set中
                    if (left.find(currentString) == left.end()) {
                        left.insert(make_pair(currentString, index));
                    }
                    //否则，说明出现了循环节
                    else {
                        cir_start = left[currentString];
                        cir_end = index - 1;
                        canStop = true;
                    }
                    //余数为0，说明除尽了
                    if (currentString == "0") {
                        canStop = true;
                    }
                    currentString += "0";
                    break;
                }
            }
            if (canStop) {
                break;
            }
        }
        return intPart + floatPart.substr(1);

    }

}
int BigNumUtil::bigDecimalCompare(string num1, string num2) {
    if (num1.size() > num2.size()) {
        return 1;
    }
    if (num1.size() < num2.size()) {
        return -1;
    }
    int ptr = 0;
    while (ptr != num1.size()) {
        if (num1[ptr] > num2[ptr]) {
            return 1;
        }
        if (num1[ptr] < num2[ptr]) {
            return -1;
        }
        ptr++;
    }
    return 0;

}
template<typename T>
vector<vector<T>> initMatrix(int m, int n, T dft) {
    vector<vector<T>> matrix;
    vector<T> row;
    row.resize(n, dft);
    matrix.resize(m, row);
    return matrix;
}
long long MathUtil::getLCM(long long a, long long b) {
    return a * b / getGCD(a, b);
}
long long MathUtil::getGCD(long long a, long long b) {
    long long max = (a > b ? a : b);
    long long min = (a < b ? a : b);
    long long res = max % min;
    while (res) {
        max = min;
        min = res;
        res = max % min;
    }
    return min;
}
unsigned long long MathUtil::powAndMod(unsigned long long const kBase, unsigned long long const kExp, unsigned long long const kMod) {
    unsigned long long ret = 1;
    for (unsigned long long i = kExp, base = kBase % kMod; i; i >>= 1) {
        if (i & 1) {
            ret = ret * base % kMod;
        }
        base = base * base % kMod;
    }
    return ret;
}
unsigned long long MathUtil::pow(unsigned long long const kBase, unsigned long long const kExp) {
    unsigned long long ret = 1;
    for (unsigned long long i = kExp, base = kBase; i; i >>= 1) {
        if (i & 1) {
            ret = ret * base;
        }
        base = base * base;
    }
    return ret;
}
unsigned long long MathUtil::exp_mod(unsigned long long a, unsigned long long b, unsigned long long p) {
    long long res = 1;
    while (b != 0) {
        if (b & 1) res = (res * a) % p;
        a = (a*a) % p;
        b >>= 1;
    }
    return res;
}
unsigned long long MathUtil::Comb(unsigned long long a, unsigned long long b, unsigned long long p) {
    if (a < b) return 0;
    if (a == b) return 1;
    if (b > a - b) b = a - b;

    unsigned long long ans = 1, ca = 1, cb = 1;
    for (unsigned long long i = 0; i < b; ++i) {
        ca = (ca * (a - i)) % p;
        cb = (cb * (b - i)) % p;
    }
    ans = (ca*exp_mod(cb, p - 2, p)) % p;
    return ans;
}
unsigned long long MathUtil::combineAndMod(unsigned long long n, unsigned long long m, unsigned long long mod) {
    unsigned long long ans = 1;

    while (n&&m&&ans) {
        ans = (ans*Comb(n%mod, m%mod, mod)) % mod;
        n /= mod;
        m /= mod;
    }
    return ans;
}
unsigned long long MathUtil::combine(int n, int m) {
    if (m < n - m) m = n - m;
    unsigned long long ans = 1;
    for (int i = m + 1; i <= n; i++) ans *= i;
    for (int i = 1; i <= n - m; i++) ans /= i;
    return ans;
}
PolynomialUtil::PolynomialUtil(int maxK, unsigned long long mod) {
    factorial.resize(maxK + 1);
    factorial[0] = 1;
    for (int i = 1; i < maxK + 1; ++i) {
        factorial[i] = factorial[i - 1] * i % mod;
    }
}
unsigned long long PolynomialUtil::go(unsigned long long a, unsigned long long b, unsigned long long k, unsigned long long n, unsigned long long m, unsigned long long mod) {
    unsigned long long inv_binom = MathUtil().powAndMod(factorial[n] * factorial[m] % mod, mod - 2, mod);
    unsigned long long apow = MathUtil().powAndMod(a, n, mod);
    unsigned long long bpow = MathUtil().powAndMod(b, m, mod);
    unsigned long long ans = factorial[k] * inv_binom % mod;
    ans = ans * apow % mod;
    ans = ans * bpow % mod;
    return ans;
}
string BigNumUtil::bigDecimalCnm(int n, int m) {
    string up = "1";
    for (int i = 0;i < m;i++) {
        up = BigNumUtil().bigDecimalMultiply(up, to_string(n - i));
    }
    string down = "1";
    for (int i = 2;i <= m;i++) {
        down = BigNumUtil().bigDecimalMultiply(down, to_string(i));
    }
    int useless;
    return BigNumUtil().bigDecimalDivide(up, down, useless, useless);
}
/*
    无循环小数：直接gcd没啥好说的
    纯循环小数:一个循环节有几个数,分母就有几个9,分子则为一个循环节上的数
    例 0.3=3/9, 0.347=347/999
    混循环小数,循环节有几个数,分母就有几个9,不循环的有几个数,分母再添几个0,分子是从不循环到一个循环节数减去不循环的数
    例 0.32=(32-3)/90, 0.2134=(2134-21)/9900
*/
void BigNumUtil::floatToFraction(string s, long long& up, long long& down) {
    auto dot = s.find('.');
    u64 a = stoull(s.substr(0, dot)), n, m;
    auto rec = s.find('[');
    if (rec == s.npos) { // 有限小数
        n = stoull(s.substr(dot + 1));
        m = u64(pow(10, s.length() - dot - 1));
    }
    else { // 循环小数
        s.erase(rec, 1);
        n = stoull(s.substr(dot + 1));
        if (dot + 1 != rec)n -= stoull(s.substr(dot + 1, rec - dot - 1));
        m = u64(pow(10, s.length() - rec - 1)) - 1;
        m *= u64(pow(10, rec - dot - 1));
    }
    auto g = MathUtil().getGCD(n, m);
    n /= g;
    m /= g;
    up = n + m * a;
    down = m;
}
void BigNumUtil::numToSci(string s, int p, string& a, string& b) {
    int power = 0;
    bool isFloat = false;
    //有小数点
    if (s.find('.') != -1) {
        isFloat = true;
        //得到整数部分
        string intPart = "";
        for (char c : s) {
            if (c != '.') {
                intPart += c;
            }
            else {
                break;
            }
        }
        //整数部分为0
        if (intPart == "0") {
            power = -1;
            int ptr = s.find('.');
            while (s[ptr] == '0' || s[ptr] == '.') {
                if (s[ptr] == '0') {
                    power--;
                }
                ptr++;
            }
            s = s.substr(ptr);
        }
        //整数部分大于等于10
        else if (BigNumUtil().bigDecimalCompare(intPart, "10") >= 0) {
            power = intPart.size() - 1;
            s.erase(s.begin() + s.find('.'));
        }
        //整数部分为1~9
        else {
            power = 0;
            s.erase(s.begin() + 1);
        }
    }
    //以下统一处理全是整数的情况
    //四舍五入
    if (s.size() > p) {
        char toBeIgnored = s[p];
        //需要向上进位
        if (toBeIgnored >= '5'&&toBeIgnored <= '9') {
            int carry = 1;
            int ptr = p - 1;
            while (true) {
                s[ptr] = s[ptr] + carry;
                if (s[ptr] > '9') {
                    s[ptr] = '0';
                    carry = 1;
                    ptr--;
                    if (ptr == -1) {
                        s.insert(s.begin(), '1');
                        power++;
                        break;
                    }
                }
                else {
                    break;
                }
            }
            string s2 = s.substr(0, p);
            if (p != 1) {
                s2.insert(s2.begin() + 1, '.');
            }
            if (isFloat) {
                a = s2;
                b = to_string(power);
            }
            else {
                a = s2;
                b = to_string(s.size() - 1);
            }
        }
        //不需要进位
        else {
            string s2 = s.substr(0, p);
            if (p != 1) {
                s2.insert(s2.begin() + 1, '.');
            }
            if (isFloat) {
                a = s2;
                b = to_string(power);
            }
            else {
                a = s2;
                b = to_string(s.size() - 1);
            }
        }
    }
    else {
        int pow = s.size();
        while (s.size() <= p) {
            s += "0";
        }
        string s2 = s.substr(0, p);
        if (p != 1) {
            s2.insert(s2.begin() + 1, '.');
        }
        if (isFloat) {
            a = s2;
            b = to_string(power);
        }
        else {
            a = s2;
            b = to_string(pow - 1);
        }
    }
}
//****************************模板END*************************************