高精度学习笔记

高精度学习笔记

先上总代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
typedef int int_;
#define int long long
const int base = 1e8;

using namespace std;

char str1[60000], str2[60000];

struct Int{
	vector<int> val;
	Int()
	{
		val.clear();
		val.resize(1, 0);
	}
	Int(char *str)
	{
		int len = strlen(str);
		int ret = 0, b = 1;
		for(int i = len - 1; i >= 0; i--)
		{
			ret += (str[i] - 48) * b;
			b *= 10;
			if((len - i) % 8 == 0)
			{
				val.push_back(ret);
				ret = 0, b = 1;
			}
		}
		val.push_back(ret);
		return ;
	}
	void clear()
	{
		while(!val.back() && val.size() > 1) val.pop_back();
	}
	int cmp(Int b)
	{
		Int a = *this, c;
		int len1 = a.val.size();
		int len2 = b.val.size();
		if(len1 < len2) return -1;
		else if(len1 > len2) return 1;
		else 
			for(int i = len1 - 1; i >= 0; i--)
			{
				if(a.val[i] < b.val[i]) return -1;
				else if(a.val[i] > b.val[i]) return 1;
			}
		return 1;
	}
	bool operator<(Int b)
	{
		Int a = *this;
		return a.cmp(b) < 0;
	}
	bool operator>(Int b)
	{
		Int a = *this;
		return a.cmp(b) > 0;
	}
	bool operator==(Int b)
	{
		Int a = *this;
		return a.cmp(b) == 0;
	}
	Int operator+(Int b)
	{
		Int a = *this, c;
		int len1 = a.val.size();
		int len2 = b.val.size();
		int len3 = max(len1, len2) + 1;
		c.val.resize(len3, 0);
		for(int i = 0; i < len3; i++)
		{
			if(i < len1) c.val[i] += a.val[i];
			if(i < len2) c.val[i] += b.val[i];
		}
		for(int i = 0; i < len3 - 1; i++)
		{
			c.val[i + 1] += c.val[i] / base;
			c.val[i] %= base;
		}
		c.clear();
		return c;
	}
	Int operator-(Int b)
	{
		Int a = *this, c;
		bool flag = 0;
		if(a < b)
		{
			swap(a, b);
			flag = 1;
		}
		int len1 = a.val.size();
		int len2 = b.val.size();
		int len3 = len1;
		c.val.resize(len3, 0);
		for(int i = 0; i < len3; i++)
			c.val[i] = a.val[i] - (i < len2 ? b.val[i] : 0);
		for(int i = 0; i < len3 - 1; i++)
		{
			if(c.val[i] < 0)
			{
				c.val[i] += base;
				c.val[i + 1]--;
			}
		}
		c.clear();
		if(flag) c.val.back() = -c.val.back();
		return c;
	}
	Int operator*(Int b)
	{
		Int a = *this, c;
		int len1 = a.val.size();
		int len2 = b.val.size();
		int len3 = len1 + len2;
		c.val.resize(len3, 0);
		for(int i = 0; i < len1; i++)
			for(int j = 0; j < len2; j++)
				c.val[i + j] += a.val[i] * b.val[j];
		for(int i = 0; i < len3 - 1; i++)
		{
			c.val[i + 1] += c.val[i] / base;
			c.val[i] %= base;
		}
		c.clear(); 
		return c;
	}
	Int operator/(Int temp)
	{
		int b = temp.val[0];
		Int a = *this, c;
		int len = a.val.size();
		c.val.resize(len, 0);
		for(int i = len - 1; i >= 1; i--)
		{
			c.val[i] = a.val[i] / b;
			a.val[i - 1] += a.val[i] % b * base;
		}
		c.val[0] = a.val[0] / b;
		c.clear();
		return c;
 	}
	void output()
	{
		int len = val.size();
		printf("%lld", val[len - 1]);
		for(int i = len - 2; i >= 0; i--)
		{
			printf("%08lld", val[i]);
		}
	}
};

int_ main() {
	scanf("%s%s", str1, str2);
	Int a(str1), b(str2), c;
	c = a + b;
	c.output();
	puts("");
	c = a - b;
	c.output();
	puts("");
	c = a * b;
	c.output();
	puts("");
	c = a / b;
	c.output();
	puts("");
	return 0;
}

上面的代码包括了 高精加 减 乘高精 以及 高精除低精

---

前置

vector<int> val;
	Int()
	{
		val.clear();
		val.resize(1, 0);
	}
	Int(char *str)
	{
		int len = strlen(str);
		int ret = 0, b = 1;
		for(int i = len - 1; i >= 0; i--)
		{
			ret += (str[i] - 48) * b;
			b *= 10;
			if((len - i) % 8 == 0)
			{
				val.push_back(ret);
				ret = 0, b = 1;
			}
		}
		val.push_back(ret);
		return ;
	}

我们定义一种 Int 代表高精类型

在定义变量时，如果单纯定义一个变量，就为它开一个长度为1的数组并将val[0]设为0

如果这个变量由字符串转换而来则将它每八位拆为一组，倒叙压入vector

void clear()
	{
		while(!val.back() && val.size() > 1) val.pop_back();
	}

这段代码是消除前导0，但保存最后一个0

---

加法

Int operator+(Int b)
	{
		Int a = *this, c;
		int len1 = a.val.size();
		int len2 = b.val.size();
		int len3 = max(len1, len2) + 1;
		c.val.resize(len3, 0);
		for(int i = 0; i < len3; i++)
		{
			if(i < len1) c.val[i] += a.val[i];
			if(i < len2) c.val[i] += b.val[i];
		}
		for(int i = 0; i < len3 - 1; i++)
		{
			c.val[i + 1] += c.val[i] / base;
			c.val[i] %= base;
		}
		c.clear();
		return c;
	}

重载运算符 +

如我们计算1 + 2

则此时b就是2；

*this 则是加号前面的变量('1')

用c.val来储存结果

用普通加法将每一位的和储存， 最后再模拟10进制进位

---

乘法

Int operator*(Int b)
	{
		Int a = *this, c;
		int len1 = a.val.size();
		int len2 = b.val.size();
		int len3 = len1 + len2;
		c.val.resize(len3, 0);
		for(int i = 0; i < len1; i++)
			for(int j = 0; j < len2; j++)
				c.val[i + j] += a.val[i] * b.val[j];
		for(int i = 0; i < len3 - 1; i++)
		{
			c.val[i + 1] += c.val[i] / base;
			c.val[i] %= base;
		}
		c.clear(); 
		return c;
	}

乘法和加法差不多

要注意位数最大是a的位数加上b的位数

在保存每一位相乘的值时，我们可以手动模拟竖式乘法计算

然后就能得出保存的位置应在i + j的位置

剩下操作与加法相同

---

减法

	Int operator-(Int b)
	{
		Int a = *this, c;
		bool flag = 0;
		if(a < b)
		{
			swap(a, b);
			flag = 1;
		}
		int len1 = a.val.size();
		int len2 = b.val.size();
		int len3 = len1;
		c.val.resize(len3, 0);
		for(int i = 0; i < len3; i++)
			c.val[i] = a.val[i] - (i < len2 ? b.val[i] : 0);
		for(int i = 0; i < len3 - 1; i++)
		{
			if(c.val[i] < 0)
			{
				c.val[i] += base;
				c.val[i + 1]--;
			}
		}
		c.clear();
		if(flag) c.val.back() = -c.val.back();
		return c;
	}

减法由于需要判断正负，我们在开始便设一个flag标记，如果被减数小于减数便互换位置并且flag = 1

第一个for循环中，我们使用一个三目运算符来判断，如果这位已经没有值了就减0

借位看代码就懂了；

最后如果flag = 1就让最开始的8位数字变负

---

除法（高精除高精太难写不会）

	Int operator/(Int temp)
	{
		int b = temp.val[0];
		Int a = *this, c;
		int len = a.val.size();
		c.val.resize(len, 0);
		for(int i = len - 1; i >= 1; i--)
		{
			c.val[i] = a.val[i] / b;
			a.val[i - 1] += a.val[i] % b * base;
		}
		c.val[0] = a.val[0] / b;
		c.clear();
		return c;
 	}

看起来短实际。。。

最后只要整除即可所以最后的c.val[0]就不管余数了

---

高精比较大小

int cmp(Int b)
	{
		Int a = *this, c;
		int len1 = a.val.size();
		int len2 = b.val.size();
		if(len1 < len2) return -1;
		else if(len1 > len2) return 1;
		else 
			for(int i = len1 - 1; i >= 0; i--)
			{
				if(a.val[i] < b.val[i]) return -1;
				else if(a.val[i] > b.val[i]) return 1;
			}
		return 1;
	}
	bool operator<(Int b)
	{
		Int a = *this;
		return a.cmp(b) < 0;
	}
	bool operator>(Int b)
	{
		Int a = *this;
		return a.cmp(b) > 0;
	}
	bool operator==(Int b)
	{
		Int a = *this;
		return a.cmp(b) == 0;
	}

---

例题 国王游戏

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
typedef int int_;
#define int long long
const int base = 1e8;

using namespace std;

char str1[60000], str2[60000];

struct Int{
	int l, r, sum;
	vector<int> val;
	Int()
	{
		val.clear();
		val.resize(1, 0);
	}
	Int(char *str)
	{
		int len = strlen(str);
		int ret = 0, b = 1;
		for(int i = len - 1; i >= 0; i--)
		{
			ret += (str[i] - 48) * b;
			b *= 10;
			if((len - i) % 8 == 0)
			{
				val.push_back(ret);
				ret = 0, b = 1;
			}
		}
		val.push_back(ret);
		return ;
	}
	void clear()
	{
		while(!val.back() && val.size() > 1) val.pop_back();
	}
	int cmp(Int b)
	{
		Int a = *this, c;
		int len1 = a.val.size();
		int len2 = b.val.size();
		if(len1 < len2) return -1;
		else if(len1 > len2) return 1;
		else 
			for(int i = len1 - 1; i >= 0; i--)
			{
				if(a.val[i] < b.val[i]) return -1;
				else if(a.val[i] > b.val[i]) return 1;
			}
		return 1;
	}
	bool operator<(Int b)
	{
		Int a = *this;
		return a.cmp(b) < 0;
	}
	bool operator>(Int b)
	{
		Int a = *this;
		return a.cmp(b) > 0;
	}
	bool operator==(Int b)
	{
		Int a = *this;
		return a.cmp(b) == 0;
	}
	Int operator*(const int b)
	{
		Int a = *this, c;
		int len1 = a.val.size();
		int len3 = len1 + 10;
		c.val.resize(len3, 0);
		for(int i = 0; i < len1; i++)
				c.val[i] += a.val[i] * b;
		for(int i = 0; i < len3 - 1; i++)
		{
			c.val[i + 1] += c.val[i] / base;
			c.val[i] %= base;
		}
		c.clear(); 
		return c;
	}
	Int operator/(const int b)
	{
		Int a = *this, c;
		int len = a.val.size();
		c.val.resize(len, 0);
		for(int i = len - 1; i >= 1; i--)
		{
			c.val[i] = a.val[i] / b;
			a.val[i - 1] += a.val[i] % b * base;
		}
		c.val[0] = a.val[0] / b;
		c.clear();
		return c;
 	}
	void output()
	{
		int len = val.size();
		printf("%lld", val[len - 1]);
		for(int i = len - 2; i >= 0; i--)
		{
			printf("%08lld", val[i]);
		}
	}
}arr[1050];

int cmp(const Int s1,const Int s2)
{
	return s1.sum < s2.sum;
}

int n;

int_ main() {
	scanf("%lld",&n);
	for(int i = 0; i <= n; i++)
	{
		scanf("%lld%lld",&arr[i].l,&arr[i].r);
		arr[i].sum = arr[i].l * arr[i].r;
	}
	sort(arr + 1, arr + 1 + n,cmp);
	Int ans, tl, temp;
	tl.val[0] = 1;
	for(int i = 0; i < n; i++)
	{
		tl = tl * arr[i].l;
		temp = tl / arr[i + 1].r;
		if(temp > ans)
			ans = temp;
	}
	ans.output();
	return 0;
}

如果理解了高精度思想很容易就能看懂

这题数学证明的出双手数字乘积越大越往后排

具体怎么证不写了

有一点害我调了很久连样例过不了

resize并不会对原vector已经存在的元素进行重新初始化！！！！！

所以最后改直接给val[0]赋值了，然后就ac了