Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"workbook":{"problemsBrief":"{\"洛谷-P1601\":[\"A+B Problem(高精)\",173998,null],\"洛谷-P1303\":[\"A*B Problem\",113877,null],\"洛谷-P1009\":[\"阶乘之和\",138419,\"NOIP1998 普及组\"],\"洛谷-P1480\":[\"A/B Problem\",35486,null],\"洛谷-P2142\":[\"高精度减法\",70813,null]}","joined":false,"groups":{}},"managingGroups":{},"author":"Exile_code","updateTime":1706767396000,"title":"基础算法入门(高精度)","dislikeCnt":0,"content":"# 基础算法入门(高精度)\n\n高精度算法,也称为大整数算法,是一类用于处理超出计算机整数范围的数字运算的算法。在计算机科学和算法竞赛中,高精度算法广泛应用于处理大数问题,如大整数的加减乘除、阶乘、组合数计算等。\n\n## 什么是高精度算法?\n\n计算机通常有限制的整数范围,例如32位系统上的整数范围是-2^31到2^31-1。当需要处理超出这个范围的整数时,就需要使用高精度算法。高精度算法的核心思想是将大整数分解为多个小整数的表示,通过模拟手工计算的方式进行运算。\n\n## 高精度算法的实现\n\n### 数组表示\n\n在高精度算法中,常用数组来表示大整数。每个数组元素存储整数的一位数字,通常按照从低位到高位的顺序排列。例如,数字123456789可以表示为数组`{9, 8, 7, 6, 5, 4, 3, 2, 1}`。\n\n### 运算规则\n\n高精度算法的运算规则与手工计算相似,包括加法、减法、乘法、除法等。\n\n- **加法**:从低位到高位逐位相加,处理进位。\n- **减法**:从低位到高位逐位相减,处理借位。\n- **乘法**:模拟手工乘法,逐位相乘并累加。\n- **除法**:模拟手工除法,逐位计算商和余数。\n\n### 进制转换\n\n在高精度算法中,常常使用进制转换来简化计算。例如,将大整数表示为每个数组元素存储多位数字,从而提高运算效率。\n\n## 应用场景\n\n### 大整数运算\n\n高精度算法常用于处理大整数的加减乘除运算,解决了计算机整数范围的限制。\n\n### 阶乘和组合数计算\n\n在计算阶乘和组合数时,结果往往非常庞大,需要使用高精度算法来确保计算的准确性。\n\n### 斐波那契数列\n\n斐波那契数列中的项随着序号增大呈指数级增长,计算时容易超出整数范围,因此需要高精度算法。\n\n### 素数筛选\n\n在素数筛选算法中,有时需要处理大整数范围内的素数,高精度算法可用于处理其中的计算。\n\n## 示例代码\n\n```cpp\n#include \u003ciostream\u003e\n#include \u003cvector\u003e\n\nusing namespace std;\n\n// 高精度加法\nvector\u003cint\u003e add(vector\u003cint\u003e\u0026 num1, vector\u003cint\u003e\u0026 num2) \n{\n vector\u003cint\u003e result;\n int carry \u003d 0;\n\n int i \u003d 0, j \u003d 0;\n while (i \u003c num1.size() || j \u003c num2.size() || carry !\u003d 0) \n {\n int x \u003d (i \u003c num1.size()) ? num1[i] : 0;\n int y \u003d (j \u003c num2.size()) ? num2[j] : 0;\n\n int sum \u003d x + y + carry;\n result.push_back(sum % 10);\n carry \u003d sum / 10;\n\n i++;\n j++;\n }\n\n return result;\n}\n\n// 高精度乘法\nvector\u003cint\u003e multiply(vector\u003cint\u003e\u0026 num1, vector\u003cint\u003e\u0026 num2) \n{\n vector\u003cint\u003e result(num1.size() + num2.size(), 0);\n\n for (int i \u003d 0; i \u003c num1.size(); ++i)\n {\n int carry \u003d 0;\n for (int j \u003d 0; j \u003c num2.size() || carry !\u003d 0; ++j) \n {\n int temp \u003d result[i + j] + num1[i] * (j \u003c num2.size() ? num2[j] : 0) + carry;\n result[i + j] \u003d temp % 10;\n carry \u003d temp / 10;\n }\n }\n\n // 去除前导零\n while (result.size() \u003e 1 \u0026\u0026 result.back() \u003d\u003d 0)\n {\n result.pop_back();\n }\n\n return result;\n}\n\n// 高精度减法\nvector\u003cint\u003e subtract(vector\u003cint\u003e\u0026 num1, vector\u003cint\u003e\u0026 num2)\n{\n vector\u003cint\u003e result;\n int borrow \u003d 0;\n\n int i \u003d 0, j \u003d 0;\n while (i \u003c num1.size() || j \u003c num2.size() || borrow !\u003d 0)\n {\n int x \u003d (i \u003c num1.size()) ? num1[i] : 0;\n int y \u003d (j \u003c num2.size()) ? num2[j] : 0;\n\n int diff \u003d x - y - borrow;\n if (diff \u003c 0) \n {\n diff +\u003d 10;\n borrow \u003d 1;\n }\n else\n borrow \u003d 0;\n\n result.push_back(diff);\n\n i++;\n j++;\n }\n\n // 去除前导零\n while (result.size() \u003e 1 \u0026\u0026 result.back() \u003d\u003d 0) \n {\n result.pop_back();\n }\n\n return result;\n}\n\n// 高精度除法\npair\u003cvector\u003cint\u003e, int\u003e divide(vector\u003cint\u003e\u0026 numerator, int denominator) {\n vector\u003cint\u003e quotient;\n int remainder \u003d 0;\n\n for (int i \u003d numerator.size() - 1; i \u003e\u003d 0; --i)\n {\n int currentDigit \u003d numerator[i] + remainder * 10;\n quotient.push_back(currentDigit / denominator);\n remainder \u003d currentDigit % denominator;\n }\n\n // 结果翻转\n reverse(quotient.begin(), quotient.end());\n\n // 去除前导零\n while (quotient.size() \u003e 1 \u0026\u0026 quotient.back() \u003d\u003d 0)\n {\n quotient.pop_back();\n }\n\n return {quotient, remainder};\n}\n\n// 示例代码\nint main() \n{\n // 示例数据\n vector\u003cint\u003e num1 \u003d {9, 9, 9, 9};\n vector\u003cint\u003e num2 \u003d {5, 4, 3, 2};\n\n // 高精度加法\n vector\u003cint\u003e sum \u003d add(num1, num2);\n cout \u003c\u003c \"结果\";\n for (int i \u003d sum.size() - 1; i \u003e\u003d 0; --i) \n {\n cout \u003c\u003c sum[i];\n }\n cout \u003c\u003c endl;\n\n // 高精度乘法\n vector\u003cint\u003e product \u003d multiply(num1, num2);\n cout \u003c\u003c \"结果: \";\n for (int i \u003d product.size() - 1; i \u003e\u003d 0; --i) \n {\n cout \u003c\u003c product[i];\n }\n cout \u003c\u003c endl;\n \n // 高精度减法\n vector\u003cint\u003e difference \u003d subtract(num1, num2);\n cout \u003c\u003c \"结果: \";\n for (int i \u003d difference.size() - 1; i \u003e\u003d 0; --i) \n {\n cout \u003c\u003c difference[i];\n }\n cout \u003c\u003c endl;\n\n // 高精度除法\n int divisor \u003d 7; // 除数\n auto divisionResult \u003d divide(num1, divisor);\n cout \u003c\u003c \"Quotient: \";\n for (int i \u003d divisionResult.first.size() - 1; i \u003e\u003d 0; --i) \n {\n cout \u003c\u003c divisionResult.first[i];\n }\n cout \u003c\u003c endl;\n cout \u003c\u003c \"结果: \" \u003c\u003c divisionResult.second \u003c\u003c endl;\n\n return 0;\n}\n```\n\n## 学习链接\n\n[高精度算法全套(加,减,乘,除,全网最详细)_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV1LA411v7mt/?vd_source\u003d204bd6a950e12dc2a5fd501f88a334d9)\n\n## 练习题目\n\n[problem:洛谷-P1601],[problem:洛谷-P2142],[problem:洛谷-P1303],[problem:洛谷-P1480],[problem:洛谷-P1009]","threadId":181201,"likeCnt":0,"createTime":1706767396000,"isWorkbook":true,"viewCnt":137,"openness":2,"fav":false,"id":4543,"trustable":false}