雖然有一個聲明叫_int128但是這并不是C++標準：
long long 不夠用？詳解 __int128 - FReQuenter - 博客園 (cnblogs.com)
網絡上去找int128的另類實現方法，發現幾乎都是在介紹_int128的
然后我就自己想了個辦法，當時還沒學C++，用C草草寫了下了事，也沒有驗證行不行
在這周一（2024/2/19）看了C++的類以及運算符重載之后，我打算拿int128來練練手
重載倒是很快練好了，但是代碼有大問題：
int128的實現（未完成）-CSDN博客
int128的實現_實現一個int128的數-CSDN博客
可以看看我之前的愚蠢的代碼
主要是完全沒注意到數爆出2^64的問題（主要體現在上面的第一篇博客，第二篇博客因為沒專門寫輸入輸出，所以沒爆掉）
還有一個非常吃屎的東西：0xFFFFFFFF這個數，是2^32-1，不是2^32
順便把輸入吞掉一個字符的問題解決了（用了ungetc函數）
說說原理吧：
總所周知，我們這里的最高位的int的位數是64位（long long），最高表示的數是2^64-1（無符號），只有18,446,744,073,709,551,615大概10的20次方，有的時候是不夠用的，用高精度數組的速度的效率又相對較慢，這時候就想到了int128了
但是只能你自己來實現（或者用上面的_int128啦，但是有的時候用不了），所以我就想了一種實現方法
用4個unsignedlonglongint值來記錄4個數，分別代表x1 * 2^96, x2 * 2 ^ 64, x3 * 2^32, x4。這樣加起來，就是一個int128的數了，而且不會爆掉（之前是用兩個數記錄高低位的，輸入輸出爆了，運算倒是沒有）
然后按照數學的計算，就可以設計出加減乘除了
代碼如下：
#ifndef CSTDIO_
#define CSTDIO_
#include<cstdio>
#endif#ifndef CCTYPE_
#define CCTYPE_
#include<cctype>
#endif#ifndef VECTOR_
#define VECTOR_
#include<vector>
#endif#ifndef INT128_H_
#define INT128_H_typedef unsigned long long LLU;//64位
typedef unsigned int U;//32位
const U MAX32 = 0xFFFFFFFF;
const LLU MAX64_U = 0xFFFFFFFF00000000;
const LLU _2POW32 = (LLU)MAX32 + 1;class INT128{LLU A, B, C, D;
public:INT128(LLU tmp = 0){A = B = 0, C = (tmp & MAX64_U) >> 32, D = tmp & MAX32;};void getnum(void);INT128 operator-(const U & tmp) const;INT128 operator+(const LLU & tmp) const;INT128 operator+(const INT128 & tmp) const;INT128 operator*(const U & tmp) const;INT128 operator/(const U & tmp) const;INT128 operator%(const U & tmp) const;void operator=(const LLU & tmp);void show(void);inline void function1(std::vector<int> & tmp, LLU & data);inline void function2(std::vector<int> & tmp, LLU & data);inline INT128 function3(INT128 & result, LLU & A1, LLU & A2, LLU & A3, LLU & A4);
};void INT128::getnum(void)
{A = B = C = D = 0;std::vector<int> tmp;char c;while(!isdigit(c = getchar()));//清空數字前面的東西do{tmp.insert(tmp.begin(), c - '0');}while(isdigit(c = getchar()));ungetc(c, stdin);//開始賦值function1(tmp, D), function1(tmp, C), function1(tmp, B);for(int i = tmp.size() - 1; i >= 0; i--)A = A * 10 + tmp[i];
}
INT128 INT128::operator-(const U & tmp) const
{LLU A1, A2, A3, A4;INT128 result(0);A1 = A, A2 = B, A3 = 0, A4 = (C << 32) + D - tmp;return function3(result, A1, A2, A3, A4);
}
INT128 INT128::operator+(const LLU & tmp) const
{LLU A1, A2, A3, A4;INT128 result(0);A1 = A, A2 = B, A3 = C, A4 = D + tmp;return function3(result, A1, A2, A3, A4);
}
INT128 INT128::operator*(const U & tmp) const
{LLU A1, A2, A3, A4;INT128 result(0);A1 = A, A2 = B, A3 = C, A4 = D;A1 *= tmp, A2 *= tmp, A3 *= tmp, A4 *= tmp;return function3(result, A1, A2, A3, A4);
}
INT128 INT128::operator/(const U & tmp) const
{LLU A1, A2, A3, A4;INT128 result(0);A1 = A, A2 = B, A3 = C, A4 = D;A2 += (A1 % tmp) << 32, A1 /= tmp;A3 += (A2 % tmp) << 32, A2 /= tmp;A4 += (A3 % tmp) << 32, A3 /= tmp;A4 /= tmp;return function3(result, A1, A2, A3, A4);
}
INT128 INT128::operator%(const U & tmp) const
{LLU A1, A2, A3, A4;INT128 result(0);A1 = A, A2 = B, A3 = C, A4 = D;A2 += (A1 % tmp) << 32;A3 += (A2 % tmp) << 32;A4 += (A2 % tmp) << 32;result.D = A4 % tmp;return result;
}
INT128 INT128::operator+(const INT128 & tmp) const
{LLU A1, A2, A3, A4;INT128 result(0);A1 = A + tmp.A, A2 = B + tmp.B, A3 = C + tmp.C, A4 = D + tmp.D;return function3(result, A1, A2, A3, A4);
}
void INT128::operator=(const LLU & tmp)
{A = B = 0, C = (tmp & MAX64_U) >> 32, D = tmp & MAX32;
}
void INT128::show(void)
{std::vector<int> tmp;//A放進數組LLU n_tmp = A;int ext = 0;while(n_tmp){tmp.push_back(n_tmp % 10);n_tmp /= 10;}//B，C，D放進數組function2(tmp, B), function2(tmp, C), function2(tmp, D);//輸出if(!tmp.size()) tmp.push_back(0);for(int i = tmp.size() - 1; i >= 0; i--)printf("%d", tmp[i]);
}
inline void INT128::function1(std::vector<int> & tmp, LLU & data)
{LLU ext = 0;bool jud = false;for(int i = tmp.size() - 1; i >= 0; i--){ext = ext * 10 + tmp[i];tmp[i] = ext / _2POW32;jud = (jud || tmp[i]) ? true : false;if(!jud) tmp.pop_back();ext %= _2POW32;}data = ext;
}
inline void INT128::function2(std::vector<int> & tmp, LLU & data)
{LLU n_tmp = 0;int ext = 0;for(int i = 0; i < tmp.size(); i++)n_tmp += _2POW32 * (LLU)tmp[i], tmp[i] = n_tmp % 10, n_tmp /= 10;while(n_tmp){tmp.push_back(n_tmp % 10);n_tmp /= 10;}n_tmp = data, ext = 0;for(int i = 0; i < tmp.size(); i++){ext += n_tmp % 10 + tmp[i];tmp[i] = ext % 10, ext /= 10, n_tmp /= 10;}n_tmp += ext;while(n_tmp){tmp.push_back(n_tmp % 10);n_tmp /= 10;}
}
inline INT128 INT128::function3(INT128 & result, LLU & A1, LLU & A2, LLU & A3, LLU & A4)
{result.D = A4 & MAX32, A3 += (A4 & MAX64_U) >> 32;result.C = A3 & MAX32, A2 += (A3 & MAX64_U) >> 32;result.B = A2 & MAX32, A1 += (A2 & MAX64_U) >> 32;result.A = A1 & MAX32;return result;
}#endif注：只有加法和賦值支持int128數，然后每種計算都支持常數，但是只有加法和賦值達到2^64-1，其他是2^32-1
至于為什么不讓每種計算都支持int128嘛，因為懶得寫了，還有乘法會爆int128、沒必要，而且藍橋杯要到了，我得加緊算法的學習了（這個東西花了我4天去改，雖然不是每一刻都在想，但是也挺搞事的）
