【C++】高精度模板大整合！高精度模板看这篇真的就够了
版本信息
| 版本号 | 版本内容 | 版本时间 |
|---|---|---|
| V 1.0.0 | 高精定义 高精加高精（普通+负数版） 高精减高精（普通+负数版） 高精乘高精（普通+负数版） 高精除高精（普通+负数版） 高精取模高精（普通+负数版） 高精加低精（普通版） 高精减低精（普通版） 高精乘低精（普通版） 高精除低精（普通版） 高精取模低精（普通版） 高精开根低精（普通版） | 2023/9/29 开工 2023/9/30 完工 |
引语
大家好！本期我们来看一下高精度的C++代码
首先感谢一下那些为我提供帮助的人，主要包括CSDN和洛谷的好心人
制作不易，求支持qwq
正文
高精度定义
高精度算法（High Accuracy Algorithm）是处理大数字的数学计算方法。在一般的科学计算中，会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数，高精度算法是用计算机对于超大数据的一种模拟加，减，乘，除，乘方，阶乘，开方等运算。对于非常庞大的数字无法在计算机中正常存储，于是，将这个数字拆开，拆成一位一位的，或者是四位四位的存储到一个数组中， 用一个数组去表示一个数字，这样这个数字就被称为是高精度数。高精度算法就是能处理高精度数各种运算的算法，但又因其特殊性，故从普通数的算法中分离，自成一家。
——百度百科
高精度op高精度
高精度加法（高精度加高精度）
普通版
#include <bits/stdc++.h>
using namespace std;
// 函数名称:add
// 函数参数:两个vector<int>
// 函数返回值:一个vector<int>
// 函数功能:返回输入的两个vector的和
// 中文名称:高精度加法
vector <int> add(vector<int> &A,vector<int> &B){
if (A.size() < B.size()) return add(B,A); // 因为下面for循环用A.size()当条件，所以现在只能让A比B长
vector<int> C;
int t = 0;
for(int i = 0;i < A.size();i++){
t += A[i];
if(i < B.size()) t += B[i]; // 判断B是否够长
C.push_back(t % 10);
t /= 10;
}
if (t) C.push_back(t);
return C;
}
// 应用部分
vector <int> A,B,C; // 请不要将这个定义放在函数上面
string CA,CB;// 因为A、B过长，所以需要使用字符串读入
int main(){
cin >> CA >> CB;
// 别忘了是逆序读入
for (int i = CA.size() - 1;i >= 0;i--) A.push_back(CA[i] - '0');
for (int i = CB.size() - 1;i >= 0;i--) B.push_back(CB[i] - '0');
C = add(A,B);
// 逆序输出
for (int i = C.size() - 1;i >= 0;i--) cout << C[i];
cout << endl;
return 0;
}能处理负数版
#include <bits/stdc++.h>
using namespace std;
// 可以处理负数
char a[1000005],b[1000005];
int fa,fb,la,lb;
void show(int ed) {
if (fa) cout << "-";
for (int i = ed;i >= fa;--i)
printf("%d",a[i]);
}
void add(){
int i,j,t = 0,s,l;
for (i = fa;i < la || i < lb;++i) {
s = a[i] + b[i] + t;
t = s / 10;
a[i] = s % 10;
}
a[i] = t;
l = t ? i : i - 1;
show(l);
}
int cmp(){
int la = strlen(a),lb = strlen(b);
if (la - fa > lb - fb) return 1;
else if (la - fa < lb - fb) return 0;
else{
int i;
for (i = 0;i < la && a[i + fa] == b[i + fb];++i);
return a[i + fa] > b[i + fb];
}
}
void minu(){
int i,j,c = 0,l = -1,s;
for (i = 0;i + fa < la;i++) {
s = a[i + fa] - b[i + fb] - c >= 0 ? 0 : 1;
a[i + fa] = (10 + a[i + fa] - b[i + fb] - c) % 10;
l = a[i + fa] ? i + fa : l,c = s;
}
if (l < 0) cout << 0;
else show(l);
}
// 应用部分
int main(){
scanf("%s%s",a,b);
fa = ('-' == a[0]), fb = ('-' == b[0]);
if (!cmp()) swap(a, b),swap(fa, fb);
la = strlen(a), lb = strlen(b);
reverse(a + fa, a + la),reverse(b + fb, b + lb);
int i = fa,j = fb;
while (i < la) a[i] -= '0',i++;
while (j < lb) b[j] -= '0',j++;
if (fa ^ fb) minu();
else add();
return 0;
}高精度减法（高精度减高精度）
普通版
#include <bits/stdc++.h>
using namespace std;
// 函数名称:cmp
// 函数参数:两个vector<int>
// 函数返回值:true或false
// 函数功能:返回输入的第一个vector<int>是否大于第二个vector<int>
// 函数备注:请与减法sub1配合使用
// 中文名称:高精度大小判断
bool cmp(vector<int> &A,vector<int> &B){
if (A.size() != B.size()) return A.size() > B.size();
for (int i = A.size() - 1;i >= 0;i++){
if (A[i] != B[i]) return A[i] > B[i];
}
return true;
}
// 函数名称:sub
// 函数参数:两个vector<int>
// 函数返回值:一个vector<int>
// 函数功能:返回输入的两个vector的差
// 函数备注:请与判断大小cmp配合使用
// 中文名称:高精度减法
vector <int> sub(vector<int> &A,vector<int> &B){
vector <int> C;
int t = 0;
for(int i = 0; i < A.size(); i++){
t = A[i] - t;
if(i < B.size()) t -= B[i];
C.push_back((t + 10) % 10); // t+10是为了避免t<0
if(t < 0) t = 1; // 借位
else t = 0; // 不借位
}
while(C.size() > 1 && C.back() == 0) C.pop_back(); //去掉前导0
return C;
}
// 应用部分
vector <int> A,B,C; // 请不要将这个定义放在函数上面
string CA,CB;// 因为A、B过长，所以需要使用字符串读入
int main(){
cin >> CA >> CB;
// 别忘了是逆序读入
for (int i = CA.size() - 1;i >= 0;i--) A.push_back(CA[i] - '0');
for (int i = CB.size() - 1;i >= 0;i--) B.push_back(CB[i] - '0');
if (cmp(A,B)){
C = sub(A,B);
for (int i = C.size() - 1;i >= 0;i--) cout << C[i];
}else{
C = sub(B,A);
cout << "-";
for (int i = C.size() - 1;i >= 0;i--) cout << C[i];
}
cout << endl;
return 0;
}能处理负数版
#include <bits/stdc++.h>
using namespace std;
string a,b,s,t;
int fa,fb;
void init(){
fa = (a[0] == '-'), fb = (b[0] == '-');
s = a.substr( 1, a.size() ), t = b.substr( 1, b.size() );
}
bool cmp(string a,string b){
int as = a.size(), bs = b.size();
if (as > bs || as == bs && a > b) return 1;
else return 0;
}
void change(string &s,string &t,string a,string b) {
int as = a.size(), bs = b.size(),d = as > bs ? as - bs : bs - as;
for (int i = 0;i < d;i++) as > bs ? t += "0" : s += "0";
s += a,t += b;
}
string cA(string a,string b){
string s = "0", t = "0";
change(s,t,a,b);
int len = s.size();
for (int i = len - 1;i >= 1;i--){
s[i] += t[i] - '0';
if (s[i] > '9') s[i] -= 10,s[i - 1]++;
}
bool j = 1;
for ( int i = 0;i < len;i++)
if (s[i] != '0') j = 0;
if (j) return "0";
return s[0] == '0' ? s.substr( 1, len ) : s;
}
string cB(string a,string b){
string s = "", t = "";
change(s,t,a,b);
if (s < t) swap(s,t);
int len = s.size();
for (int i = len - 1;i >= 0;i--){
if (s[i] < t[i]){
s[i] += 10;
if (s[i - 1] >= '1') s[i - 1]--;
else{
int j = i - 1;
while (s[j] == '0') s[j--] += 9;
s[j]--;
}
}
s[i] -= (t[i] - '0');
}
if (len == 1) return s;
return s[0] == '0' ? cA(s.substr(1,len),"0") : s;
}
// 应用部分
int main() {
cin >> a >> b;
init();
if (fa && fb){
if (cmp(s, t)) cout << "-";
cout << cB(s,t) << endl;
}else if (!fa && !fb){
if (!cmp(a, b) ) cout << "-";
cout << cB(a,b) << endl;
}else if (fa) cout << "-" << cA(s,b) << endl;
else cout << cA(a,t) << endl;
return 0;
}高精度乘法（高精度乘高精度）
普通版
#include <bits/stdc++.h>
using namespace std;
// 函数名称:mul
// 函数参数:两个vector<int>
// 函数返回值:一个vector<int>
// 函数功能:返回输入的两个vector的积
// 中文名称:高精度乘法
vector <int> mul(vector <int> &A, vector <int> &B) {
vector <int> C(A.size() + B.size(), 0);
for (int i = 0; i < A.size(); i ++) {
for (int j = 0; j < B.size(); j ++){
C[i + j] += A[i] * B[j];
C[i + j + 1] += C[i + j] / 10;
C[i + j] %= 10;
}
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
// 应用部分
vector <int> A,B,C;
string CA,CB; // 字符串存储
int main(){
cin >> CA >> CB;
for (int i = CA.size() - 1;i >= 0;i--) A.push_back(CA[i] - '0');
for (int i = CB.size() - 1;i >= 0;i--) B.push_back(CB[i] - '0');
C = mul(A,B);
for (int i = C.size() - 1;i >= 0;i--) cout << C[i];
cout << endl;
return 0;
}能处理负数版
#include <bits/stdc++.h>
using namespace std;
// 可以处理负数版
const int T = 1000000;
char a1[T],b1[T];
int a[T],b[T],c[T],lena,lenb,lenc,x,t,f;
void mul() {
for (int i = 1;i <= lena;i++) {
x = 0; //x是进位
for (int j = 1;j <= lenb;j++) {
c[i + j - 1] += a[i] * b[j] + x;
x = c[i + j - 1] / 10;
c[i + j - 1] %= 10;
}
c[i + lenb] = x;
}
lenc = lena + lenb;
while (c[lenc] == 0 && lenc > 1) lenc--;
if (f == -1) cout << "-";
for (int i = lenc;i >= 1;i--) cout << c[i];
cout << endl;
}
// 应用部分
int main() {
cin >> a1 >> b1 ;
lena = strlen(a1), lenb = strlen(b1);
f = 1, t = 0;
if (a1[0] == '-') f *= -1, t++;
for (int i = t;i <= lena - 1;i++) a[lena - i] = a1[i] - '0'; // 转换为int
t = 0;
if (b1[0] == '-') f *= -1,t++;
for (int i = t;i <= lenb - 1;i++) b[lenb - i] = b1[i] - '0';
mul();
return 0;
}高精度除法（高精度除高精度）
普通版（带余数）
#include <bits/stdc++.h>
using namespace std;
// 减法部分
int a[101],b[101],c[101],d,i;
void inp(int a[]){ // 读入
string s;
cin >> s; //读入字符串
a[0] = s.size(); //a[0]储存字符串的长度
for (i = 1;i <= a[0];i++) a[i] = s[a[0] - i] - '0';
}
void pri(int a[]){ // 输出
if (a[0] == 0){
cout << "0" << endl;
return;
}
for (i = a[0];i > 0;i--) cout << a[i];
cout << endl;
return;
}
int cmp(int a[],int b[]){//比较a和b的大小关系，若a>b则为1，若a<b则为-1，若a=b则为0
if (a[0] > b[0]) return 1; //若a的位数大于b，则a>b
if (a[0] < b[0]) return -1; //若a的位数小于b，则a<b
for (i = a[0];i > 0;i--){
if (a[i] > b[i]) return 1;
if (a[i] < b[i]) return -1;
}
return 0;
}
void jian(int a[],int b[]){
int pd = cmp(a,b); // 比较大小
if (pd == 0){ // 相等
a[0] = 0;
return;
}else if (pd == 1){
for (i = 1;i <= a[0];i++){
if (a[i] < b[i]) a[i + 1]--,a[i] += 10; // 借位
if (a[i] >= b[i]) a[i] -= b[i];
}
while((a[a[0]] == 0) && (a[0] > 0)) a[0]--;
return;
}
}
void numcpy(int p[],int q[],int det){
for (i = 1;i <= p[0];i++) q[i + det - 1] = p[i];
q[0] = p[0] + det - 1;
}
void chugao(int a[],int b[],int c[]){
int i,tmp[101];
c[0] = a[0] - b[0] + 1;
for (i = c[0];i > 0;i--){
memset(tmp,0,sizeof(tmp));
numcpy(b,tmp,i);
while (cmp(a,tmp) >= 0){
c[i]++;
jian(a,tmp);
}
}
while((c[c[0]] == 0) && (c[0] > 0)) c[0]--;
}
// 应用部分
int main(){
inp(a),inp(b);
chugao(a,b,c);
pri(c),pri(a);
return 0;
}能处理负数版（不带余数，见取模）
#include <bits/stdc++.h>
using namespace std;
// 此版本无法输出余数，求余数见高精度取模
string fixedNum(string a) {
if (a.size() == 1) return a;
for (int i = 0;i < a.size();i++){
if ('1' <= a[i] && a[i] <= '9') return a.substr( i, a.size() );
}
return "0";
}
string cA(string a,string b) {
a = fixedNum(a),b = fixedNum(b);
int as = a.size(), bs = b.size(), d = as > bs ? as - bs : bs - as;
string s = "0", t = "0";
for (int i = 0;i < d;i++) as > bs ? t += "0" : s += "0";
s += a,t += b;
for (int i = s.size() - 1;i >= 1;i--){
s[i] += t[i] - '0';
if (s[i] > '9') s[i] -= 10,s[i - 1]++;
}
return s[0] == '0' ? s.substr( 1, s.size() ) : s;
}
string cS(string a, string b){
int as = a.size(), bs = b.size(), d = as - bs;
string s = "", t = "";
for (int i = 0;i < d;i++) t += "0";
s += a,t += b;
for (int i = s.size() - 1;i >= 0;i--) {
if (s[i] < t[i]) {
s[i] += 10;
if (s[i - 1] >= '1') s[i - 1]--;
else {
int j = i - 1;
while (s[j] == '0') s[j--] += 9;
s[j]--;
}
}
s[i] -= (t[i] - '0');
}
if (s.size() == 1) return s;
for (int i = 0;i < s.size();i++){
if ('1' <= s[i] && s[i] <= '9') return s.substr(i,s.size());
}
return "0";
}
// 应用部分
int main() {
string a, b, c, sum = "0", cnt = "1";
bool j1 = 0;
cin >> a >> b;
if (a == "0"){
cout << 0 << endl;
return 0;
}else if (a[0] == '-' && b[0] == '-') a = a.substr(1,a.size()),b = b.substr(1,b.size());
else if (a[0] == '-') j1 = 1,a = a.substr(1, a.size());
else if (b[0] == '-') j1 = 1,b = b.substr(1, b.size());
c = b;
int as = a.size(),bs = b.size(), cs, d = as - bs;
for (int i = 0;i < d - 1;i++) c += "0",cnt += "0";
cs = c.size();
bool j2 = 0;
while (c != b) {
while (as > cs || as == cs && a >= c) j2 = 1,a = cS(a,c),as = a.size(),sum = cA(sum,cnt);
c = c.substr(0,c.size() - 1),cnt = cnt.substr(0,cnt.size() - 1),cs = c.size();
}
while (as > bs || as == bs && a >= b) j2 = 1,a = cS(a,b),sum = cA(sum,cnt),as = a.size();
if (j1 && j2) cout << '-';
cout << sum << endl;
return 0;
}高精度取模（高精度取模高精度）
普通版
在高精度除法（普通版）中作为余数实现，此处不再重复
能处理负数版
#include <bits/stdc++.h>
using namespace std;
// 可以处理负数版
string cA(string a,string b){
int as = a.size(), bs = b.size(), d = as > bs ? as - bs : bs - as;
string s = "0", t = "0";
for (int i = 0;i < d;i++) as > bs ? t += "0" : s += "0";
s += a,t += b;
for ( int i = s.size() - 1; i >= 1; i-- ) {
s[i] += t[i] - '0';
if (s[i] > '9') s[i] -= 10,s[i - 1]++;
}
bool j = true;
for (int i = 0;i < s.size();i++)
if (s[i] != '0') j = false;
if (j) return "0";
return s[0] == '0' ? s.substr( 1, s.size() ) : s;
}
string cS(string a,string b){
int as = a.size(), bs = b.size(), d = as - bs;
string s = "", t = "";
for (int i = 0;i < d;i++) t += "0";
s += a,t += b;
for (int i = s.size() - 1;i >= 0;i--){
if (s[i] < t[i]){
s[i] += 10;
if (s[i - 1] >= '1') s[i - 1]--;
else{
int j = i - 1;
while (s[j] == '0') s[j--] += 9;
s[j]--;
}
}
s[i] -= (t[i] - '0');
}
if (s.size() == 1) return s;
for ( int i = 0; i < s.size(); i++ ) {
if ('1' <= s[i] && s[i] <= '9') return s.substr(i,s.size());
}
return "0";
}
// 应用部分
int main() {
string a, b, c;
cin >> a >> b;
c = b;
int as = a.size(), bs = b.size(),cs,d = as - bs;
for (int i = 0;i < d - 1;i++) c += "0";
cs = c.size();
while ( c != b ) {
while (as > cs || as == cs && a >= c) a = cS(a,c),as = a.size();
c = c.substr(0,c.size() - 1),cs = c.size();
}
while (as > bs || as == bs && a >= b) a = cS(a,b),as = a.size();
cout << a << endl;
return 0;
}高精度op低精度
高精度加低精度
#include <bits/stdc++.h>
using namespace std;
// 函数名称:add
// 函数参数:一个vector<int>和一个int变量
// 函数返回值:一个vector<int>
// 函数功能:返回输入的一个vector和一个int的和
// 中文名称:高精度加低精度
vector<int> add(vector<int> &A, int b){
vector<int> C;
int t = A.size();
A[0] += b;
for(int i = 0;i < t - 1; i ++){
C.push_back(A[i] % 10);
A[i + 1] += A[i] / 10;
}
if (A[t - 1] > 0){
C.push_back(A[t - 1] % 10);
A[t - 1] /= 10;
}
return C;
}
// 应用部分
vector <int> A,C;
string CA;
int b;
int main(){
cin >> CA >> b;
for (int i = CA.size() - 1;i >= 0;i--) A.push_back(CA[i] - '0');
C = add(A,b);
for (int i = C.size() - 1;i >= 0;i--) cout << C[i];
cout << endl;
return 0;
}高精度减低精度
#include <bits/stdc++.h>
using namespace std;
// 函数名称:sub
// 函数参数:一个vector<int>和一个int变量
// 函数返回值:一个vector<int>
// 函数功能:返回输入的一个vector和一个int的差
// 中文名称:高精度减低精度
vector<int> sub(vector<int> A, int b){
int t = A.size();
A[0] -= b;
for (int i = 0;i < t - 1; i ++){
if (A[i] < 0){
int x = (( -1 * A[i] ) / 10 + 1);
A[i] += x * 10;
A[i + 1] -= x;
}
}
while (A.size() > 1 && A.back() == 0) A.pop_back();
return A;
}
// 应用部分
vector <int> A,C;
string CA;
int b;
int main(){
cin >> CA >> b;
for (int i = CA.size() - 1;i >= 0;i--) A.push_back(CA[i] - '0');
C = sub(A,b);
for (int i = C.size() - 1;i >= 0;i--) cout << C[i];
cout << endl;
return 0;
}高精度乘低精度
#include <bits/stdc++.h>
using namespace std;
// 函数名称:mul2
// 函数参数:一个vector<int>和一个int变量
// 函数返回值:一个vector<int>
// 函数功能:返回输入的一个vector和一个int的积
// 中文名称:高精度乘低精度
vector <int> mul(vector <int> & A, int b) {
vector <int> C;
int t = 0;
for (int i = 0; i < A.size(); i ++) {
t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
while (t){
C.push_back(t % 10);
t /= 10;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
// 应用部分
vector <int> C,A;
string a;
int b;
int main() {
cin >> a >> b;
for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');
C = mul(A,b);
for (int i = C.size() - 1; i >= 0; i --) cout << C[i];
return 0;
}高精度除低精度
#include <bits/stdc++.h>
using namespace std;
// 函数名称:mul2
// 函数参数:一个vector<int>和一个int变量
// 函数返回值:一个vector<int>
// 函数功能:返回输入的一个vector和一个int的积
// 中文名称:高精度乘低精度
vector <int> mul(vector <int> &A,int b,int &r) {
vector <int> C;
r = 0;
for (int i = A.size() - 1;i >= 0;i--){
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
reverse(C.begin(),C.end());
while(C.size() > 1 && C.back() == 0) C.pop_back(); //去掉前导0
return C;
}
// 应用部分
vector <int> C,A;
string a;
int b,r; // 不要漏了r，r是余数
int main() {
cin >> a >> b;
for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');
C = mul(A,b,r);
for (int i = C.size() - 1; i >= 0; i --) cout << C[i];
cout << endl << r << endl;
return 0;
}高精度取模低精度
#include <bits/stdc++.h>
using namespace std;
// 高精度取模低精度
int mod(string a,int b){
int d = 0;
for(int i = 0;i < a.size();i++) d = (d * 10 + (a[i] - '0')) % b; //求出余数
return d;
}
// 应用部分
string a;
int b;
int main(){
cin >> a >> b;
cout << mod(a,b);
return 0;
}高精度开根低精度
感谢这位dalao
#include <bits/stdc++.h>
#define Ll unsigned long long
// 感谢洛谷的dalao
using namespace std;
const Ll NN = 1e9;
const int N = 9;
struct H{
Ll a[1500],len;
H(){
memset(a,0,sizeof a);
len = 1;
}
};
int n;
H s;
void init(H &a){//读入
string s;
cin >> s;
int l;
a.len = 0;
for(int r = s.size() - 1;r >= 0;r -= N){
a.len++;
if(r >= N - 1) l = r - N + 1;
else l = 0;
for(int i = l;i <= r;i++) a.a[a.len] = a.a[a.len] * 10 + s[i] - '0';
}
}
void outit(H a){//输出
cout << a.a[a.len];
for(int i = a.len - 1;i;i--){
for(int k = NN / 10;a.a[i] < k;k /= 10) cout << 0;
if(a.a[i]) cout << a.a[i];
}
cout << endl;
}
void in(H &a,int x){
if(!x)return;
a.len = 0;
while(x) a.a[++a.len] = x % NN,x /= NN;
}
bool bigD(H a,H b){ // 比较
if(a.len > b.len) return 1;
if(a.len < b.len) return 0;
for(int i = a.len;i;i--){
if(a.a[i] != b.a[i]){
if(a.a[i] > b.a[i]) return 1;
else return 0;
}
}
return 1;
}
H jia(H a,H b){
H c;
int l = max(a.len,b.len);
for(int i = 1;i <= l;i++){
c.a[i] += a.a[i] + b.a[i];
c.a[i+1] = c.a[i] / NN;
c.a[i] %= NN;
}
if(c.a[l + 1]) l++;
c.len = l;
return c;
}
H chu(H a){
H c;
if(a.len == 1){
c.a[1] = a.a[1] >> 1;
return c;
}
for(int i = a.len;i;i--){
if(a.a[i] & 1ll)a.a[i-1] += NN;
c.a[i] = a.a[i] >> 1;
}
if(c.a[a.len]) c.len = a.len;
else c.len = a.len - 1;
return c;
}
H rrr(H a){
if(a.len == 1) a.a[1]--;return a;
H c = a;
c.a[1]--;
int l = 1;
while(c.a[l] < 0) c.a[l] = NN - 1,c.a[++l]--;
if(!c.a[c.len]) c.len--;
return c;
}
H chen(H a,H b){
H z;
z.len = a.len + b.len + 2;
for(int i = 1;i <= a.len;i++){
for(int j = 1;j <= b.len;j++) z.a[i + j - 1] += (a.a[i] * b.a[j]);
}
for(int i = 1;i <= z.len;i++) z.a[i + 1] += z.a[i] / NN,z.a[i] %= NN;
while(z.len > 1 && !z.a[z.len]) z.len--;
return z;
}
H ksm(H a,int n){
if(n == 1) return a;
H c = ksm(a,n >> 1);
c = chen(c,c);
if(n & 1) c = chen(c,a);
return c;
}
bool Chu(H a){
if(a.len * n - n + 1 > s.len) return 0;
if(bigD(s,ksm(a,n))) return 1;
return 0;
}
// 应用部分
int main(){
cin >> n;
init(s);
if(n == 1){
outit(s);
return 0;
}
H l,r,mid,ans;
in(l,1);
r = s;
while(bigD(r,l)){
mid = jia(l,r);
mid = chu(mid);
if(Chu(mid)){
if(bigD(mid,ans)) ans = mid;
H c;
in(c,1);
l = jia(mid,c);
}else{
r = rrr(mid);
}
}
outit(ans);
return 0;
}高精度浮点数
#include<bits/stdc++.h>
using namespace std;
// 高精浮点数
const int SIZE=264000;
complex<double> e[SIZE],A[SIZE],w1[SIZE],w2[SIZE];
void DFT(complex<double> *A, complex<double> *w, int l, int r, int dt){
int N = r - l; // 全检长度
if (N == 1){
w[l] = A[l];
return;
}
int N1 = N >> 1,mid = (l + r) >> 1,pos1 = l,pos2 = mid;
for (int i = 0; i < N; i++){
if (i & 1) w[pos2] = A[i + l],pos2++;
else w[pos1] = A[i + l],pos1++;
}
DFT(w,A,l,mid,dt << 1),DFT(w,A,mid,r,dt << 1);
for (int i = 0;i < N1;i++) w[l + i] = A[l + i] + e[i*dt] * A[i + mid],w[i + mid] = A[l + i] - e[i*dt] * A[i + mid];
}
struct Wfloat{
const static int size = SIZE;
int *a,length,sign,pos;
Wfloat(){
a = (int*)malloc(sizeof(int)* size);
a[0] = 0,length = 1,sign = 0,pos = 0;
}
Wfloat(const Wfloat &ans){
a = (int*)malloc(sizeof(int)* size);
length = ans.length,sign = ans.sign,pos = ans.pos;
for (int i = 0;i < length;i++) a[i] = ans.a[i];
}
Wfloat(char *word){
a = (int*)malloc(sizeof(int)* size);
int wordlength = strlen(word);
pos = 0,length = 0,sign = 0;
for (int i = wordlength - 1; i >= 0; i--){
char c = word[i];
if (c == '.') pos = length + 1;
else if (c == '-') sign = 1;
else a[length] = c - '0',length++;
}
}
Wfloat operator = (const Wfloat &ans){
length = ans.length,sign = ans.sign,pos = ans.pos;
for (int i = 0; i < length; i++) a[i] = ans.a[i];
return *this;
}
Wfloat operator =(char *word){ // 无小数点
int wordlength = strlen(word);
pos = 0,length = 0,sign = 0;
for (int i = wordlength - 1; i >= 0; i--){
char c = word[i];
if (c == '.') pos = length + 1;
else if (c == '-') sign = 1;
else a[length] = c - '0',length++;
}
return *this;
}
~Wfloat(){free(a);}
};
void Print(const Wfloat &ans){
if (ans.sign == 1) cout << "-";
if (ans.pos >= ans.length){
cout << "0.";
for (int i = 0;i < ans.pos - ans.length;i++) cout << "0";
for (int i = ans.length - 1;i >= 0;i--) cout << ans.a[i];
}else{
for (int i = ans.length - 1;i >= ans.pos;i--) cout << ans.a[i];
if (ans.pos != 0){
cout << ".";
for (int i = ans.pos - 1;i >= 0;i--) cout << ans.a[i];
}
}
cout << endl;
}
Wfloat operator * (const Wfloat &number1, int number2){
Wfloat ans = number1;
if (number2 < 0) ans.sign = -number1.sign,number2 = -number2;
for (int i = 0;i < ans.length;i++) ans.a[i] *= number2;
for (int i = 0;i < ans.length;i++){
if (ans.a[i] >= 10){
if (i == ans.length - 1) ans.length++,ans.a[i + 1] = 0;
ans.a[i + 1] += ans.a[i] / 10.ans.a[i] %= 10;
}
}
return ans;
}
Wfloat operator / (const Wfloat &number1, int number2){
Wfloat answer;
int lastnumber = 0,length = -1;
for (int i = number1.length - 1;i >= 0;i--){
lastnumber *= 10,lastnumber += number1.a[i],answer.a[i] = lastnumber / number2,lastnumber -= answer.a[i] * number2;
if (length == -1 && answer.a[i] != 0) length = i + 1;
}
answer.length = length,answer.pos = number1.pos,answer.sign = number1.sign;
return answer;
}
Wfloat Multiplication(const Wfloat &number1, const Wfloat &number2, int eps){
Wfloat ans;
double pi = 3.1415926535897932384626;
int length1 = min(eps, number1.length),length2 = min(eps, number2.length);
if (length1 > 1000 && length2 > 1000){
int tempLength = max(length1 / 3, length2 / 3),N = 1;
while (N < tempLength) N <<= 1;
N <<= 1;
for (int i = 0; i < N; i++) e[i] = complex<double>(cos(2 * pi * i / N), sin(2 * pi * i / N));
int lastPos;
for (int i = 0; i < length1; i++){
lastPos = i / 3;
if (i % 3 == 0) A[lastPos] = complex<double>(number1.a[number1.length - length1 + i], 0);
else if (i % 3 == 1) A[lastPos] += complex<double>(number1.a[number1.length - length1 + i] * 10.0, 0);
else if (i % 3 == 2) A[lastPos] += complex<double>(number1.a[number1.length - length1 + i] * 100.0, 0);
}
for (int i = lastPos + 1; i < N; i++) A[i] = complex<double>(0, 0);
DFT(A, w1, 0, N, 1);
for (int i = 0; i < length2; i++){
lastPos = i / 3;
if (i % 3 == 0) A[lastPos] = complex<double>(number2.a[number2.length - length2 + i], 0);
else if (i % 3 == 1) A[lastPos] += complex<double>(number2.a[number2.length - length2 + i] * 10.0, 0);
else if (i % 3 == 2) A[lastPos] += complex<double>(number2.a[number2.length - length2 + i] * 100.0, 0);
}
for (int i = lastPos + 1; i < N; i++) A[i] = complex<double>(0, 0);
DFT(A, w2, 0, N, 1);
for (int i = 0;i < N;i++) w2[i] *= w1[i];
for (int i = 0;i < N;i++) e[i] = complex<double>(cos(-2 * pi * i / N), sin(-2 * pi * i / N));
DFT(w2,w1,0,N,1);
long long temp = 0,temp1 = 0;
for (int i = 0;i < N;i++){
temp += w1[i].real() / N + 0.001,temp1 = temp / 1000,temp %= 1000;
ans.a[i * 3] = temp % 10,ans.a[i * 3 + 1] = temp % 100 / 10,ans.a[i * 3 + 2] = temp / 100;
temp = temp1;
if (ans.a[i * 3 + 2] != 0) ans.length = i * 3 + 3;
else if (ans.a[i * 3 + 1] != 0) ans.length = i * 3 + 2;
else if (ans.a[i * 3] != 0) ans.length = i * 3 + 1;
}
ans.pos = number1.pos + number2.pos - (number1.length - length1 + number2.length - length2),ans.sign = number1.sign^number2.sign;
return ans;
}else{
int length3 = length1 + length2 + 4;
for (int i = 0;i < length3;i++) ans.a[i] = 0;
ans.length = 0;
for (int i = 0;i < length1;i++){
int number = number1.a[number1.length - length1 + i];
for (int j = 0; j < length2; j++) ans.a[i + j] += number2.a[number2.length - length2 + j] * number,ans.length = max(ans.length, i + j + 1);
}
for (int k = 0;k < ans.length;k++){
if (ans.a[k] >= 10){
if (k == ans.length - 1) ans.length++;
ans.a[k + 1] += ans.a[k] / 10,ans.a[k] %= 10;
}
}
ans.pos = number1.pos + number2.pos - (number1.length - length1 + number2.length - length2),ans.sign = number1.sign^number2.sign;
return ans;
}
}
Wfloat Multiplication(const Wfloat &number3, const Wfloat &number4){
Wfloat number1 = number3,number2 = number4,ans;
int eps = max(number1.length, number2.length),length1 = number1.length,length2 = number2.length;
if (length1 > length2){
int length3 = length1 - length2;
for (int i = 0; i < length3; i++) number2.a[number2.length] = 0,number2.length++;
}else if (length1 < length2){
int length3 = length2 - length1;
for (int i = 0;i < length3;i++) number1.a[number1.length] = 0,number1.length++;
}
ans = Multiplication(number1, number2,eps);
int temp = ans.length - ans.pos;
for (int i = 0;i < temp;i++) ans.a[i] = ans.a[ans.pos + i];
ans.length = temp,ans.pos = 0;
return ans;
}
Wfloat Subtraction(const Wfloat &number3, const Wfloat &number4, int eps){
Wfloat number1 = number3,number2 = number4,ans;
int tempLength = eps,length1 = number1.pos - number1.length,length2 = number2.pos - number2.length;
if (length1 > length2){
int length3 = length1 - length2;
for (int i = 0;i < length3;i++) number1.a[number1.length] = 0,number1.length++;
}else if (length1 < length2){
int length3 = length2 - length1;
for (int i = 0;i < length3;i++) number2.a[number2.length] = 0,number2.length++;
}
int pos = 1;
for (int i = tempLength - 1; i >= 0; i--){
int b1,b2;
if (number1.length - pos < 0) b1 = 0;
else b1 = number1.a[number1.length - pos];
if (number2.length - pos < 0) b2 = 0;
else b2 = number2.a[number2.length - pos];
ans.a[i] = b1 - b2;
pos++;
}
int length = 0;
for (int i = 0; i < tempLength; i++){
if (ans.a[i] < 0) ans.a[i + 1]--,ans.a[i] += 10;
if (ans.a[i] != 0) length = i;
}
length++;
ans.length = length,ans.pos = number1.pos - number1.length + tempLength;
return ans;
}
Wfloat Subtraction(const Wfloat &number1, const Wfloat &number2){
Wfloat ans;
int eps = max(number1.length, number2.length);
ans = Subtraction(number1, number2, eps);
int temp = ans.length - ans.pos;
for (int i = 0;i < temp;i++) ans.a[i] = ans.a[ans.pos + i];
ans.length = temp,ans.pos = 0;
return ans;
}
Wfloat Reciprocal(const Wfloat &N, int eps1){
Wfloat ans;
if (N.pos == 0){ // 整数
Wfloat x0, x1;
int N1length = N.length;
int Effectbit = 16;
Effectbit = min(Effectbit, N.length);
int lastZero = N1length - Effectbit;
double num = 0;
for (int i = 1; i <= Effectbit; i++) num *= 10,num += N.a[N1length - i];
x0.pos = lastZero;
num = pow(num, -1);
int tempNum,count1 = 0,flag = 0;
x0.length = 16;
int n1 = 15;
while (count1 < 16){
num *= 10,tempNum = num;
if (tempNum != 0) num -= tempNum;
if (tempNum == 0 && flag == 0) x0.pos++;
else flag = 1,x0.a[n1] = tempNum,n1--,x0.pos++;
if (flag) count1++;
}
int lastbiteps = eps1;
int biteps = 32;
while (1){
x1 = Multiplication(N, x0, biteps);
x1 = Multiplication(x1, x0, biteps);
x0 = Subtraction(x0 * 2, x1, biteps);
if (biteps > lastbiteps) break;
biteps *= 2;
}
ans = x0;
return ans;
}
return ans;
}
Wfloat Division(const Wfloat &number1, const Wfloat &number2, int eps){
Wfloat ans;
return ans;
}
Wfloat Division(const Wfloat &number1, const Wfloat &number2){
Wfloat ans;
if (number1.length < number2.length) return ans;
int eps = number1.length - number2.length + 50;
ans = Reciprocal(number2, eps),ans = Multiplication(ans, number1, eps);
int temp = ans.length - ans.pos;
for (int i = 0; i < temp; i++) ans.a[i] = ans.a[ans.pos + i];
ans.length = temp;
ans.pos = 0;
return ans;
}
Wfloat sqrt(Wfloat &N){
Wfloat ans;
if (N.sign == 1) return ans;
if (N.pos == 0){ // 整数
int eps = 50;
Wfloat x0, x1;
int N1length = N.length,Effectbit = 16;
Effectbit = min(Effectbit, N.length);
int lastZero = N1length - Effectbit;
double num = 0;
for (int i = 1; i <= Effectbit; i++) num *= 10,num += N.a[N1length - i];
if (lastZero % 2 != 0) num *= 10,Effectbit++,lastZero--;
x0.pos = lastZero / 2;
num = pow(num, -0.5);
int tempNum,count1 = 0,flag = 0,n1 = 15;
x0.length = 16;
while (count1 < 16){
num *= 10,tempNum = num;
if (tempNum != 0) num -= tempNum;
if (tempNum == 0 && flag == 0) x0.pos++;
else flag = 1,x0.a[n1] = tempNum,n1--,x0.pos++;
if (flag) count1++;
}
int lastbiteps = N.length / 2 + eps;//最终需要的精度
int biteps = 32;
x0.a[1]--;
if (x0.a[1] < 0){
for (int i = 1;; i++){
if (x0.a[i] < 0) x0.a[i + 1]--,x0.a[i] += 10;
else break;
}
}
while (1){
x1 = Multiplication(N, x0, biteps),x1 = Multiplication(x1, x0, biteps),x1.a[x1.pos] = 3,x1.length = x1.pos + 1;
for (int i = 0;i < x1.pos;i++) x1.a[i] = -x1.a[i];
for (int i = 0;i < x1.pos;i++){
if (x1.a[i] < 0) x1.a[i] += 10,x1.a[i + 1]--;
}
x1.length = x1.pos + 1,x1 = x1 / 2,x1 = Multiplication(x0, x1, biteps),x0 = x1;
if (biteps > lastbiteps) break;
biteps *= 2;
}
ans = Multiplication(x0, N, lastbiteps);
int temp = ans.length - ans.pos;
for (int i = 0;i < temp;i++) ans.a[i] = ans.a[ans.pos + i];
ans.length = temp;
ans.pos = 0;
return ans;
}
}
double Reciprocal(double a){
double x0 = 0.2,x1;
while (1){
x1 = 2 * x0 - a * x0 * x0;
if (abs(x0 - x1) < 1e-15) break;
printf("%.16lf\n", x1);
getchar();
swap(x0, x1);
}
return x1;
}
// 应用部分
char word[100100];
int main(){
Wfloat A, B;
scanf("%s", word);
A = word;
scanf("%s", word);
B = word;
Wfloat ans = Division(A, B);
Print(ans);
ans = Subtraction(A, Multiplication(ans, B));
Print(ans);
}
转自这里
高精度低精度互转
#include <bits/stdc++.h>
using namespace std;
// 对于这份代码的to_string函数，版本低的C++识别不出来
vector<int> int_to_vec(int in){
string str = to_string(in);
vector<int> res;
for (int i = str.size() - 1;i >= 0;i--) res.push_back(str[i] - '0');
return res;
}
int vec_to_str(vector<int> &A){ // 请确保int能装下
string res;
for (int i = 0;i < A.size();i++) res += to_string(A[i]);
reverse(res.begin(),res.end());
return stoi(res);
}
vector<int> mul(vector<int> &A, vector<int> &B){ // 用乘法示范
vector<int> C(A.size() + B.size(), 0);
for (int i = 0; i < A.size(); i++) {
for (int j = 0;j < B.size();j++){
C[i + j] += A[i] * B[j];
if (C[i + j] >= 10){
C[i + j + 1] += C[i + j] / 10;
C[i + j] %= 10;
}
}
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
// 应用部分
int CA,CB;
int main(){
cin >> CA >> CB;
vector <int> A = int_to_vec(CA);
vector <int> B = int_to_vec(CB);
int result = vec_to_str(A) + vec_to_str(B); // 用加法当范例
vector <int> C = mul(A,B); // 用乘法测试
cout << vec_to_str(A) << endl << vec_to_str(B) << endl;
for (int i = A.size() - 1;i >= 0;i--) cout << A[i];
cout << endl;
for (int i = B.size() - 1;i >= 0;i--) cout << B[i];
cout << endl;
for (int i = C.size() - 1;i >= 0;i--) cout << C[i];
cout << endl;
cout << result << endl;
return 0;
}结语
求支持！
还是感谢一下那些为我提供帮助的人
此外，还有什么没有嘛？可以告诉我一下，我要是能找到就补充上去