0
已解决
初级启示者
__int128是c++（64位编译器）中提供的一个隐藏的数据类型，可以存放下（-2^127）~（2^127-1）的超大数字（当然，相对于高精度来说微不足道，但是时间复杂度和正常运算几乎相同（应该能水掉一些题目）），不过cin/cout不支持__int128类型的输入输出（并且部分标准库函数也不支持__int128），所以我自己封装了一个int128类使用，并提供了一些方便的函数
#include <bits/stdc++.h>
namespace std {
class int128 {
private:
__int128 data;
void read(__int128 &n) {
__int128 x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
n = x * f;
}
void print(__int128 n) {
if (n < 0) {
putchar('-');
n *= -1;
}
if (n > 9) print(n / 10);
putchar(n % 10 + '0');
}
public:
int128() { //默认构造
data = 0;
}
int128(__int128 n) { //赋值（__int128）构造
data = n;
}
int128(const int128 &n) { //赋值（int128）构造
data = n.data;
}
int128(string n) { //赋值（字符串）构造
int l = n.size();
data = 0;
for (int i = 0; i < l; i++) {
if (n[i] != '-') {
data *= 10;
data += n[i] - '0';
}
}
if (n[0] == '-') {
data *= -1;
}
}
int128(const char n[]) { //赋值（字符数组）构造
int l = strlen(n);
data = 0;
for (int i = 0; i < l; i++) {
if (n[i] != '-') {
data *= 10;
data += n[i] - '0';
}
}
if (n[0] == '-') {
data *= -1;
}
}
template<typename T> int128(T n) { //赋值（默认类型）构造
data = n;
}
const int128 operator=(__int128 n) { //赋值（__int128）
data = n;
return *this;
}
const int128 operator=(int128 n) { //赋值（int128）
data = n.data;
return *this;
}
const int128 operator=(string n) { //赋值（字符串）
int l = n.size();
data = 0;
for (int i = 0; i < l; i++) {
if (n[i] != '-') {
data *= 10;
data += n[i] - '0';
}
}
if (n[0] == '-') {
data *= -1;
}
return *this;
}
const int128 operator=(const char n[]) { //赋值（字符数组）
int l = strlen(n);
data = 0;
for (int i = 0; i < l; i++) {
if (n[i] != '-') {
data *= 10;
data += n[i] - '0';
}
}
if (n[0] == '-') {
data *= -1;
}
return *this;
}
template<typename T> const int128 operator=(T n) { //赋值（默认类型）
data = n;
return *this;
}
const int128 operator+(int128 n) { //加法运算（int128）
int128 tmp;
tmp.data = data + n.data;
return tmp;
}
const int128 operator-(int128 n) { //减法运算（int128）
int128 tmp;
tmp.data = data - n.data;
return tmp;
}
const int128 operator*(int128 n) { //乘法运算（int128）
int128 tmp;
tmp.data = data * n.data;
return tmp;
}
const int128 operator/(int128 n) { //除法运算（int128）
int128 tmp;
tmp.data = data / n.data;
return tmp;
}
const int128 operator%(int128 n) { //取模运算（int128）
int128 tmp;
tmp.data = data % n.data;
return tmp;
}
template<typename T> const int128 operator+(T n) { //加法运算（默认类型）
int128 tmp;
tmp.data = data + n;
return tmp;
}
template<typename T> const int128 operator-(T n) { //减法运算（默认类型）
int128 tmp;
tmp.data = data - n;
return tmp;
}
template<typename T> const int128 operator*(T n) { //乘法运算（默认类型）
int128 tmp;
tmp.data = data * n;
return tmp;
}
template<typename T> const int128 operator/(T n) { //除法运算（默认类型）
int128 tmp;
tmp.data = data / n;
return tmp;
}
template<typename T> const int128 operator%(T n) { //取模运算（默认类型）
int128 tmp;
tmp.data = data % n;
return tmp;
}
template<typename T> const int128 operator+=(T n) { //加等于运算（默认类型）
data += n;
return *this;
}
template<typename T> const int128 operator-=(T n) { //减等于运算（默认类型）
data -= n;
return *this;
}
template<typename T> const int128 operator*=(T n) { //乘等于运算（默认类型）
data *= n;
return *this;
}
template<typename T> const int128 operator/=(T n) { //除等于运算（默认类型）
data /= n;
return *this;
}
template<typename T> const int128 operator%=(T n) { //模等于运算（默认类型）
data %= n;
return *this;
}
const int128 operator++() { //自增运算（前缀）
data++;
return *this;
}
const int128 operator++(int) { //自增运算（后缀）
int128 tmp = *this;
data++;
return tmp;
}
const int128 operator--() { //自减运算（前缀）
data--;
return *this;
}
const int128 operator--(int) { //自减运算（后缀）
int128 tmp = *this;
data--;
return tmp;
}
template<typename T> const bool operator==(T n) { //判断等于
return data == n;
}
template<typename T> const bool operator!=(T n) { //判断不等于
return data != n;
}
template<typename T> const bool operator>(T n) { //判断大于
return data > n;
}
template<typename T> const bool operator<(T n) { //判断小于
return data < n;
}
template<typename T> const bool operator>=(T n) { //判断大于等于
return data >= n;
}
template<typename T> const bool operator<=(T n) { //判断小于等于
return data <= n;
}
operator __int128() const { //隐式类型转换为__int128
return data;
}
__int128 &get_data() { //获取可修改的__int128;
return data;
}
const string get_str() { //取得string类型
__int128 t = (data >= 0) ? (data) : (-data);
string tmp = "";
while (t != 0) {
tmp = char(t % 10 + '0') + tmp;
t /= 10;
}
if (data < 0) {
tmp = "-" + tmp;
}
return tmp;
}
friend istream &operator>>(istream &in, int128 &n) { //cin输入
n.read(n.data);
return in;
}
friend ostream &operator<<(ostream &out, int128 n) { //cout输入
__int128 tmp = n.data;
n.print(tmp);
return out;
}
};
const int128 abs(__int128 n) { //绝对值（标准库不支持__int128）
int128 tmp = (n >= 0) ? (n) : (-n);
return tmp;
}
void swap(int128 &a, int128 &b) { //交换值（使用位运算，高速）
a.get_data() ^= b;
b.get_data() ^= a;
a.get_data() ^= b;
}
}
using namespace std;
int main() {
//用就完了！！
int128 a = 245634656, b = "-22819675368796518726325";
int128 c = a + b, d = b % a;
c++, --d;
string s = d.get_str();
cout << c << endl << s;
return 0;
}测试（洛谷：P1601 A+B Problem（高精））
高精度：
int128：
水了80分！！（题目：a,b≤10^500）（懒狗水题专用）（而且时间复杂度和空间复杂度都明显小于高精度）
又及：实测可以存下斐波那契数列到第184个数字
0
已采纳
新手光能
歇了吧
//王牌工作室产品：LongNum
#ifndef LONGNUM_H_
#define LONGNUM_H_
#include<string>
#include<sstream>
#include<istream>
#include<ostream>
#include<algorithm>
#include<cmath>
#include<exception>
using std::string;
using std::istream;
using std::ostream;
using std::fill;
using std::sqrt;
using std::exception;
class NumberIsNanException : public exception
{
public:
virtual const char *what(){return "NumberIsNan";}
};
class LongNum
{
string shu;
string jia(string a, string b){
if(a=="Nan" ||b=="Nan") throw NumberIsNanException();
string ans;
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
a.push_back('0'); b.push_back('0');
if(a.size() < b.size()) swap(a, b);
while(b.size() < a.size()) b.push_back('0');
int c[1000]={0}, k = a.size();
for(int i = 0; i < a.size(); i++)
{
int s = c[i] + a[i]-'0' + b[i] - '0';
c[i] = s%10;
c[i+1] += s/10;
}
while(c[k]==0 && k>=0) k--;
while(k >= 0)
ans.push_back(c[k--]+'0');
return ans;
}
string jian(string a, string b){
if(a=="Nan" ||b=="Nan") throw NumberIsNanException();
string ans;
bool flag = false;
if(a.size() < b.size() || (a.size()==b.size() && a < b)){
swap(a, b);
flag = true;
}
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
a.push_back('0'); b.push_back('0');
if(a.size() < b.size()) swap(a, b);
while(b.size() < a.size()) b.push_back('0');
int c[1000]={0}, k = a.size();
for(int i = 0; i < a.size(); i++){
if(a[i] < b[i]) a[i]+=10, a[i+1]--;
c[i] = a[i] - b[i];
}
while(c[k]==0 && k>=0) k--;
if(flag) ans.push_back('-');
while(k >= 0)
ans.push_back(c[k--]+'0');
return ans;
}
string cheng(string a, string b){
if(a=="Nan" ||b=="Nan") throw NumberIsNanException();
string ans;
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int c[1000]={0}, k = a.size()+b.size()+1;
for(int i = 0; i < a.size(); i++){
for(int j = 0; j < b.size(); j++){
c[i+j] += (a[i]-'0')*(b[j]-'0');
c[i+j+1] += c[i+j]/10;
c[i+j] %= 10;
}
}
while(c[k]==0 && k>=0) k--;
while(k >= 0){
ans.push_back(c[k--]+'0');
}
return ans;
}
string chu(string a, long long b){
if(a=="Nan") throw NumberIsNanException();
int z[256] = {0}, d = 0;
for(int i = 0; i < a.size(); i++)
{
d = 10*d + a[i] - '0';
z[i] = d / b;
d %= b;
}
string ans;
int len = 0;
while(z[len] == 0 && len < a.size()-1)
len++;
for(int i = len; i < a.size(); i++){
ans.push_back(z[i]+'0');
}
return ans;
}
int sub1(int *a, int *b, int La, int Lb){
if (La < Lb)
return -1;//如果a小于b，则返回-1
if (La == Lb) {
for (int i = La - 1; i >= 0; i--)
if (a[i] > b[i])
break;
else if (a[i] < b[i])
return -1;//如果a小于b，则返回-1
}
for (int i = 0; i < La; i++) //高精度减法
{
a[i] -= b[i];
if (a[i] < 0)
a[i] += 10, a[i + 1]--;
}
for (int i = La - 1; i >= 0; i--)
if (a[i])
return i + 1;//返回差的位数
return 0;//返回差的位数
}
string yu(string n1, string n2){
if(n1=="Nan" ||n2=="Nan") throw NumberIsNanException();
int nn=2;
string s, v;//s存商,v存余数
int a[100010], b[100010], r[100010],
La = n1.size(), Lb = n2.size(), i, tp = La;
fill(a, a + 100010, 0);
fill(b, b + 100010, 0);
fill(r, r + 100010, 0);
for (i = La - 1; i >= 0; i--)
a[La - 1 - i] = n1[i] - '0';
for (i = Lb - 1; i >= 0; i--)
b[Lb - 1 - i] = n2[i] - '0';
if (La < Lb || (La == Lb && n1 < n2)) {
return n1;
}
int t = La - Lb;
for (int i = La - 1; i >= 0; i--)
if (i >= t)
b[i] = b[i - t];
else
b[i] = 0;
Lb = La;
for (int j = 0; j <= t; j++) {
int temp;
while ((temp = sub1(a, b + j, La, Lb - j)) >= 0)
{
La = temp;
r[t - j]++;
}
}
for (i = 0; i < 100010 - 10; i++)
r[i + 1] += r[i] / 10, r[i] %= 10;
while (!r[i])
i--;
while (i >= 0)
s += r[i--] + '0';
i = tp;
while (!a[i])
i--;
while (i >= 0)
v += a[i--] + '0';
if (v.empty())
v = "0";
return v;
}
string toString(long long n){
std::ostringstream sout;
sout<<n;
return sout.str();
}
unsigned long long toInt(string s){
std::istringstream sin;
long long n;
sin>>n;
return n;
}
public:
LongNum(){shu="Nan";}
LongNum(string s="0"){shu=s;}
LongNum(int n){shu=toString(n);}
LongNum(long long n){shu=toString(n);}
LongNum(float) = delete;
LongNum(double) = delete;
LongNum(const LongNum&) = default;
operator string(){return shu;}
LongNum&operator=(string s){shu=s;return *this;}
LongNum&operator=(int n){shu=toString(n);return *this;}
LongNum&operator=(long long n){shu=toString(n);return *this;}
LongNum&operator=(float) = delete;
LongNum&operator=(double) = delete;
LongNum operator+(const LongNum&ln) {return jia(shu,ln.shu);}
LongNum operator-(const LongNum&ln) {return jian(shu,ln.shu);}
LongNum operator*(const LongNum&ln) {return cheng(shu,ln.shu);}
LongNum operator/(const long long&ll) {return chu(shu,ll);}
LongNum operator%(const LongNum&ln) {return yu(shu,ln.shu);}
LongNum operator+=(const LongNum&ln) {shu=jia(shu,ln.shu);return *this;}
LongNum operator-=(const LongNum&ln) {shu=jian(shu,ln.shu);return *this;}
LongNum operator*=(const LongNum&ln) {shu=cheng(shu,ln.shu);return *this;}
LongNum operator/=(const long long&ll) {shu=chu(shu,ll);return *this;}
LongNum operator%=(const LongNum&ln) {shu=yu(shu,ln.shu);return *this;}
LongNum operator++(){this->operator+=(1);return *this;}
LongNum operator++(int){LongNum t=*this;this->operator+=(1);return t;}
LongNum operator--(){this->operator-=(1);return *this;}
LongNum operator--(int){LongNum t=*this;this->operator-=(1);return t;}
friend istream&operator>>(istream&is,LongNum&ln);
friend ostream&operator<<(ostream&os,LongNum ln);
friend bool operator< (LongNum x,LongNum y);
friend bool operator<=(LongNum x,LongNum y);
friend bool operator> (LongNum x,LongNum y);
friend bool operator>=(LongNum x,LongNum y);
friend bool operator==(LongNum x,LongNum y);
};
istream&operator>>(istream&is,LongNum&ln)
{
is>>ln.shu;
return is;
}
ostream&operator<<(ostream&os,LongNum ln)
{
os<<ln.shu;
return os;
}
bool operator< (LongNum x,LongNum y)
{
if(x.shu.size()!=y.shu.size())
return x.shu.size()<y.shu.size();
return x.shu<y.shu;
}
bool operator> (LongNum x,LongNum y)
{
return y<x;
}
bool operator==(LongNum x,LongNum y)
{
return x.shu==y.shu;
}
/*
LongNum sqrt(LongNum ln)
{
for(LongNum i=1;i<ln+1;i++)
{
if(i*i==ln) return i;
}
return LongNum("Nan");
}
*/
#endif
王牌工作室官方在2022-03-05 14:48:03追加了内容
其实已经被修订n次了
后面可能继续修订
