高精度

简介

高精度算法普遍日渐落后于时代
Python 和 Java 都支持无限精度整数
高精度算法的考查几乎只能在中国看到

int, long long类型都是有范围的，万一需要处理更大范围的数字怎么办呢？
int <= 2e9 == 2**31 - 1
long long <= 9e18 == 2**63 - 1
只能手动模拟，或者使用其他语言(Python 或 Java)。

存储

用数组存，先存低位，再存高位，比如a[0]存个位，a[1]存十位。
a[i]对应的系数是10i10^i，计算起来比较方便。

整个数字有多少位，可以不存，即认为处理的数字高位有00；
也可以存下来，并且在运算中维护，优化运算效率。

00有时算作一位数，有时算作零位数，视情况而定。

读入

先把整个数字读入，然后翻转，每个位置减去字符'0'。
这样的写法可以方便的进行压位操作。

输出

先确定位数

输出最高位（同时处理0的情况）

从高位到低位依次输出（如果用到压位，需处理前导0的情况）

加法

直接模拟即可，最后扫一遍，处理进位。
建议把运算和处理进位借位用两个循环实现。

nn位数加mm位数，结果可能有 max⁡(n,m)\max(n, m) 或 max⁡(n,m)+1\max(n, m)+1 位。

比较大小

先比较位数，如果位数相等，从高位到低位依次比较。

也可以不考虑位数，直接从高位到低位依次比较（不存在的位认为是0）

减法

只允许大的减去小的

直接模拟即可，最后扫一遍，处理借位。
建议把运算和处理借位用两个循环实现。

最后要去掉前导零，特别注意结果为0的情况

乘法

直接模拟即可，最后扫一遍，处理进位。

nn位数乘以mm位数，结果可能有 n+mn + m 或 n+m−1n + m - 1 位。
还有可能其中一个乘数是 00。

FFT优化

可以用FFT优化。但是优化很小，因为高精度乘法可以压位优化，
但是FFT后就不能压位了。

高精度除模单精度

高精度对一个范围比较小的数字的取模是一个比较简单的问题
扫一遍模拟即可

高精度除高精度

不能使用笔算的试除法
一般使用二分即可

进制转换

将一个ll位的高精度的数字从AA进制转化为BB进制。
如果存在整数nn和mm使得An=BmA^n = B^m那么可以将AA进制的数字，每nn位一组，一起转化为mm位的BB进制，时间复杂度是O(l)O(l)的。
如果不满足以上条件，那么就只能每次模BB除以BB依次获得BB进制下的每一位数字了。

分治FFT优化进制转换

一些高精度语言，比如Ruby用了更快的算法（分治）

高精度小数

往往通过乘以10的次幂的形式转化为整数

高精度开根

高精度最大公约数

压位

进制的范围，只要不太大（比如不超过int类型）计算的复杂度是差不多的。
所以相对于十进制来说，更加常用的是万进制，甚至是10910^9进制，这样可以加快计算。

int范围高达2e9，所以可以使用万进制或者亿进制存储，输出时需要特殊处理前导0和0的情况。

其他语言

因为Java, Python等语言均支持高精度，高精度在在线算法比赛出现的概率并不高。
当然也有一些比谁手写高精度快的题目，比如算高精度Pi。

Java nextProbablePrime

Java 可以用 nextProbablePrime 来找到 >n 最小的质数

参考题目

P1601 A+B Problem（高精）

https://www.luogu.com.cn/problem/P1601

题目描述

高精度加法，相当于a+b problem，不用考虑负数.

输入格式

分两行输入。a,b≤10500a,b \leq 10^{500}

输出格式

输出只有一行，代表a+ba+b的值

样例 #1

样例输入 #1
1
1
样例输出 #1
2

样例 #2

样例输入 #2
1001
9099
样例输出 #2
10100

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
char a[1020];
char b[1020];
char c[1020];
int main() {
	scanf("%s%s", a, b);
	int la = strlen(a);
	int lb = strlen(b);
	reverse(a, a + la);
	reverse(b, b + lb);
	for (int i = 0; i < la; i++) {
		a[i] -= '0';
	}
	for (int i = 0; i < lb; i++) {
		b[i] -= '0';
	}
	int lc = max(la, lb);
	for (int i = 0; i < lc; i++) {
		c[i] = a[i] + b[i];
	}
	for (int i = 0; i < lc; i++) {
		while (c[i] >= 10) {
			c[i] -= 10;
			c[i + 1] += 1;
		}
	}
	if (c[lc] > 0) {
		lc++;
	}
	for (int i = lc - 1; i >= 0; i--) {
		printf("%d", c[i]);
	}
	printf("\n");
	return 0;
}

题解

高精度加法

P2142 高精度减法

https://www.luogu.com.cn/problem/P2142

题目描述

高精度减法。

输入格式

两个整数 a,ba,b（第二个可能比第一个大）。

输出格式

结果（是负数要输出负号）。

样例 #1

样例输入 #1
2
1
样例输出 #1
1

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
string A, B;
int a[10020];
int b[10020];
bool cmp(const string &A, const string &B) {
	if (A.size() != B.size()) {
		return A.size() < B.size();
	}
	return A < B;
}
int main() {
	cin >> A >> B;
	if (cmp(A, B)) {
		swap(A, B);
		printf("-");
	}
	for (int i = 0; i < A.size(); i++) {
		a[i] = A[A.size() - i - 1] - '0';
	}
	for (int i = 0; i < B.size(); i++) {
		b[i] = B[B.size() - i - 1] - '0';
	}
	for (int i = 0; i < B.size(); i++) {
		a[i] -= b[i];
	}
	for (int i = 0; i < A.size(); i++) {
		while (a[i] < 0) {
			a[i] += 10;
			a[i + 1]--;
		}
	}
	int l = A.size();
	while (l > 0 && a[l] == 0) {
		l--;
	}
	for (int i = l; i >= 0; i--) {
		printf("%d", a[i]);
	}
	printf("\n");
	return 0;
}

题解

高精度减法

P1303 A*B Problem

https://www.luogu.com.cn/problem/P1303

题目描述

求两数的积。

输入格式

两行，两个整数。

输出格式

一行一个整数表示乘积。

样例 #1

样例输入 #1
1 
2
样例输出 #1
2

提示

每个数字不超过 10200010^{2000} ，需用高精。

参考代码

#include <bits/stdc++.h>
using namespace std;
char s[4020];
int a[4020];
int b[4020];
int c[4020];
int main() {
	scanf("%s", s);
	int la = strlen(s);
	for (int i = 0; i < la; i++) {
		a[i] = s[i] - '0';
	}
	reverse(a, a + la);

	scanf("%s", s);
	int lb = strlen(s);
	for (int i = 0; i < lb; i++) {
		b[i] = s[i] - '0';
	}
	reverse(b, b + lb);

	int lc = la + lb;
	for (int i = 0; i < la; i++) {
		for (int j = 0; j < lb; j++) {
			c[i + j] += a[i] * b[j];
		}
	}
	for (int i = 0; i < lc; i++) {
		c[i + 1] += c[i] / 10;
		c[i] %= 10;
	}
	while (lc > 1 && c[lc - 1] == 0) {
		lc--;
	}
	for (int i = lc - 1; i >= 0; i--) {
		printf("%d", c[i]);
	}
	printf("\n");
	return 0;
}

题解

高精度乘法

P1480 A/B Problem

https://www.luogu.com.cn/problem/P1480

题目描述

输入两个整数 a,ba,b，输出它们的商。

输入格式

两行，第一行是被除数，第二行是除数。

输出格式

一行，商的整数部分。

样例 #1

样例输入 #1
10
2
样例输出 #1
5

提示

0≤a≤1050000\le a\le 10^{5000}，1≤b≤1091\le b\le 10^9。

参考代码

#include <bits/stdc++.h>
using namespace std;
char s[5020];
int a[5020];
int b;
int main() {
	scanf("%s%d", s, &b);
	int n = strlen(s);
	for (int i = 0; i < n; i++) {
		a[i] = s[n - i - 1] - '0';
	}
	int u = 0;
	for (int i = n - 1; i >= 0; i--) {
		u = u * 10 + a[i];
		a[i] = u / b;
		u %= b;
	}
	while (n > 1 && a[n - 1] == 0) {
		n--;
	}
	for (int i = n - 1; i >= 0; i--) {
		printf("%d", a[i]);
	}
	printf("\n");
}

题解

高精度除以单精度

P1255 数楼梯

https://www.luogu.com.cn/problem/P1255

题目描述

楼梯有 NN 阶，上楼可以一步上一阶，也可以一步上二阶。

编一个程序，计算共有多少种不同的走法。

输入格式

一个数字，楼梯数。

输出格式

输出走的方式总数。

样例 #1

样例输入 #1
4
样例输出 #1
5

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
int a[3020], b[3020];
void swap() { // jiaohuan a he b
	for (int i = 0; i < 3010; i++) {
		swap(a[i], b[i]);
	}
}
void add() { // a += b
	for (int i = 0; i < 3010; i++) {
		a[i] += b[i];
	}
	for (int i = 0; i < 3010; i++) {
		a[i + 1] += a[i] / 10;
		a[i] %= 10;
	}
}

int main() {
	a[0] = 1;
	b[0] = 1;
	scanf("%d", &n);
	if (n == 0) {
		printf("0\n");
		return 0;
	}
	for (int i = 0; i < n; i++) { // a, b   -> b, a + b
		add();
		swap();
	}
	int l = 3010;
	while (a[l] == 0) {
		l--;
	}
	for (int i = l; i >= 0; i--) {
		printf("%d", a[i]);
	}
	printf("\n");
	return 0;
}

题解

高精度加法算Fibonacci数，n=0n=0的情况非常智障，答案是00而不是11。

P1080 [NOIP2012 提高组] 国王游戏

https://www.luogu.com.cn/problem/P1080

题目描述

恰逢 HH国国庆，国王邀请nn 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 nn 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

输入格式

第一行包含一个整数nn，表示大臣的人数。

第二行包含两个整数 aa和 bb，之间用一个空格隔开，分别表示国王左手和右手上的整数。

接下来 nn行，每行包含两个整数aa 和 bb，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。

输出格式

一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

样例 #1

样例输入 #1
3 
1 1 
2 3 
7 4 
4 6
样例输出 #1
2

提示

【输入输出样例说明】

按11、22、33 这样排列队伍，获得奖赏最多的大臣所获得金币数为 22；

按 11、33、22 这样排列队伍，获得奖赏最多的大臣所获得金币数为22；

按 22、11、33 这样排列队伍，获得奖赏最多的大臣所获得金币数为 22；

按22、33、11这样排列队伍，获得奖赏最多的大臣所获得金币数为99；

按 33、11、22这样排列队伍，获得奖赏最多的大臣所获得金币数为 22；

按33、22、11 这样排列队伍，获得奖赏最多的大臣所获得金币数为 99。

因此，奖赏最多的大臣最少获得 22个金币，答案输出 22。

【数据范围】

对于 20%的数据，有 1≤n≤10,0<a,b<81≤ n≤ 10,0 < a,b < 8；

对于 40%的数据，有1≤n≤20,0<a,b<81≤ n≤20,0 < a,b < 8；

对于 60%的数据，有 1≤n≤1001≤ n≤100；

对于 60%的数据，保证答案不超过 10910^9；

对于 100%的数据，有 1≤n≤1,000,0<a,b<100001 ≤ n ≤1,000,0 < a,b < 10000。

NOIP 2012 提高组 第一天 第二题

参考代码

题解

国王游戏。按乘积排序然后计算答案。
需要高精度或 Python

P1727 计算π

https://www.luogu.com.cn/problem/P1727

题目背景

《爱与愁的故事第二弹·compute》第一章。

题目描述

中秋至，博饼声铿锵不断。爱与愁大神兴致勃勃地到学校博饼，结果抱回家的只有一秀二举。爱与愁大神十分生气，打电话给月落乌啼：“喂，帮我算出圆周率小数点后n（n<=10000）位，速度……”然后就挂了电话，也不知道月落乌啼正准备去上课。月落乌啼只好请到了你，让你编一个程序求出圆周率小数点后n位。

输入格式

只有一行：n

输出格式

若干行。

第一行：3.

第二行开始：圆周率的小数部分。10个数一个空格，50个数一次回车。

样例 #1

样例输入 #1
100
样例输出 #1
3.
1415926535 8979323846 2643383279 5028841971 6939937510
5820974944 5923078164 0628620899 8628034825 3421170679

提示

对于 30%30\% 的数据，n≤103n\leq 10^3。

对于 100%100\% 的数据，n≤104n\leq 10^4。

时限：1∼61\sim 6 点 11 秒，77 点 33 秒，88 点 88 秒，9∼109\sim 10 点 1212 秒。

参考代码

题解

算Pi，用
https://en.wikipedia.org/wiki/Machin-like_formula
的公式

P1729 计算e

https://www.luogu.com.cn/problem/P1729

题目背景

《爱与愁的故事第二弹·compute》最终章。

自然对数的底数e是一个著名的无理数，其近似值为2.718281828…有计算e的公式如下：

 ![](https://cdn.luogu.com.cn/upload/pic/520.png)

e=∑n=0∞1n!e=\sum_{n=0}^{\infty}\frac{1}{n!}

其中n!表示n的阶乘，即n!=1*2*3*…*n。

题目描述

月落乌啼竟然这么快就回复了圆周率小数点后10000位？！不可能，他肯定求了别人。爱与愁大神再次为难月落乌啼：“帮我算一算e后n（n<=10000）位，速度！！！”月落乌啼想求别人，结果他发现由于刚才跟你通话已经用完了手机的所有电。关键时刻只能靠自己。如果现在你是他，你会怎么编这个程序？

输入格式

只有一行：n

输出格式

若干行。

第一行：2.

第二行开始：e的小数部分。10个数一个空格，50个数一次回车。

样例 #1

样例输入 #1
100
样例输出 #1
2.
7182818284 5904523536 0287471352 6624977572 4709369995
9574966967 6277240766 3035354759 4571382178 5251664274

提示

30%数据：n<=1000

100%数据：n<=10000

时限：全部1秒

参考代码

题解

算E，用定义就可以了。

P1096 [NOIP2007 普及组] Hanoi 双塔问题

https://www.luogu.com.cn/problem/P1096

题目描述

给定AA、BB、CC三根足够长的细柱，在AA柱上放有2n2n个中间有孔的圆盘，共有nn个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的（下图为n=3n=3的情形）。

现要将这些圆盘移到CC柱上，在移动过程中可放在BB柱上暂存。要求：

（1）每次只能移动一个圆盘；

（2）AA、BB、CC三根细柱上的圆盘都要保持上小下大的顺序；

任务：设AnA_n为2n2n个圆盘完成上述任务所需的最少移动次数，对于输入的nn，输出AnA_n。

输入格式

一个正整数nn，表示在AA柱上放有2n2n个圆盘。

输出格式

一个正整数, 为完成上述任务所需的最少移动次数AnA_n。

样例 #1

样例输入 #1
1
样例输出 #1
2

样例 #2

样例输入 #2
2
样例输出 #2
6

提示

【限制】

对于50%50\%的数据，1≤n≤251 \le n \le 25

对于100%100\%的数据，1≤n≤2001 \le n \le 200

【提示】

设法建立AnA_n与An−1A_{n-1}的递推关系式。

参考代码

#include <bits/stdc++.h>
using namespace std;
stringstream ss;
string s;
int n;
int main() {
	cin >> n;
	ss << fixed << setprecision(0) << pow(2, n + 1);
	ss >> s; // s = ss.str();
	s[s.size() - 1] -= 2;
	cout << s << endl;
	return 0;
}

题解

输入nn，输出2(2n−1)2(2^n - 1)，可以利用精确输出double的特性。

P1760 通天之汉诺塔

https://www.luogu.com.cn/problem/P1760

题目背景

直达通天路·小A历险记第四篇

题目描述

在你的帮助下，小A成功收集到了宝贵的数据，他终于来到了传说中连接通天路的通天山。但是这距离通天路仍然有一段距离，但是小A突然发现他没有地图！！！但是幸运的是，他在山脚下发现了一个宝箱。根据经验判断（小A有经验吗？），地图应该就在其中！在宝箱上，有三根柱子以及在一根柱子上的n个圆盘。小A在经过很长时间判断后，觉得这就是hanoi塔！（这都要琢磨）。但是移动是需要时间的，所以小A必须要通过制造延寿药水来完成这项任务。现在，他请你告诉他需要多少步完成，以便他造足够的延寿药水.。时限1s。

输入格式

一个数n，表示有n个圆盘

输出格式

一个数s，表示需要s步。

样例 #1

样例输入 #1
31
样例输出 #1
2147483647

样例 #2

样例输入 #2
15
样例输出 #2
32767

提示

对于所有数据n<=15000

很容易的练手题哦！

参考代码

#include <bits/stdc++.h>
using namespace std;
int a[5020];
int b[5020];
int main() {
	int n;
	scanf("%d", &n);
	a[0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 5010; j++) {
			a[j] *= 2;
		}
		for (int j = 0; j < 5010; j++) {
			a[j + 1] += a[j] / 1000000000;
			a[j] %= 1000000000;
		}
	}
	int l = 5010;
	while (a[l] == 0) {
		l--;
	}
	a[0]--;
	printf("%d", a[l]);
	for (int j = l - 1; j >= 0; j--) {
		printf("%09d", a[j]);
	}
	printf("\n");
	return 0;
}

题解

输入nn，输出2n−12^n - 1，可以利用精确输出double的特性。

Error: ENOENT: no such file or directory, open '/Users/wwwwodddd/Dropbox/Github/Informatics/problems/CF1700B.md'

CF1144E Median String

https://codeforces.com/problemset/problem/1144/E
https://www.luogu.com.cn/problem/CF1144E

参考代码

题解

abc174_c Repsept

https://atcoder.jp/contests/abc174/tasks/abc174_c
输入K，问最小连续几个7组成的数字，是K的倍数？无解输出-1

参考代码

#include <bits/stdc++.h>
using namespace std;
int k, a;
int main()
{
	cin >> k;
	for (int i = 1; i <= k; i++)
	{
		a = (10 * a + 7) % k;
		if (a == 0)
		{
			cout << i << endl;
			return 0;
		}
	}
	cout << -1 << endl;
	return 0;
}

题解

abc233_e Σ[k=0..10^100]floor(X／10^k)

https://atcoder.jp/contests/abc233/tasks/abc233_e
输入一个数字X，问所有前缀和是多少？
比如输入 1225 应该输出 1225 + 122 + 12 + 1 = 1360

参考代码

#include <bits/stdc++.h>
using namespace std;
string s;
int n, a[500020];
int main()
{
	cin >> s;
	reverse(s.begin(), s.end());
	n = s.size();
	for (int i = 0; i < n; i++)
	{
		a[i] = s[i] - '0';
	}
	for (int i = n - 1; i >= 0; i--)
	{
		a[i] += a[i + 1];
	}
	n += 1;
	for (int i = 0; i < n; i++)
	{
		a[i + 1] += a[i] / 10;
		a[i] %= 10;
	}
	while (a[n - 1] == 0)
	{
		n--;
	}
	for (int i = n - 1; i >= 0; i--)
	{
		cout << a[i];
	}
	cout << endl;
	return 0;
}

题解

  1. 高精度
    1. 简介
    2. 存储
    3. 读入
    4. 输出
    5. 加法
    6. 比较大小
    7. 减法
    8. 乘法
      1. FFT优化
    9. 高精度除模单精度
    10. 高精度除高精度
    11. 进制转换
      1. 分治FFT优化进制转换
    12. 高精度小数
    13. 高精度开根
    14. 高精度最大公约数
    15. 压位
    16. 其他语言
      1. Java nextProbablePrime
    17. 参考题目
      1. P1601 A+B Problem（高精）
      2. P2142 高精度减法
      3. P1303 A*B Problem
      4. P1480 A/B Problem
      5. P1255 数楼梯
      6. P1080 [NOIP2012 提高组] 国王游戏
      7. P1727 计算π
      8. P1729 计算e
      9. P1096 [NOIP2007 普及组] Hanoi 双塔问题
      10. P1760 通天之汉诺塔
      11. CF1144E Median String
      12. abc174_c Repsept
      13. abc233_e Σ[k=0..10^100]floor(X／10^k)
≡