版本信息

版本号	版本内容	版本时间
V 1.0.0	高精定义 高精加高精（普通+负数版） 高精减高精（普通+负数版） 高精乘高精（普通+负数版） 高精除高精（普通+负数版） 高精取模高精（普通+负数版） 高精加低精（普通版） 高精减低精（普通版） 高精乘低精（普通版） 高精除低精（普通版） 高精取模低精（普通版） 高精开根低精（普通版）	2023/9/29 开工 2023/9/30 完工

引语

大家好！本期我们来看一下高精度的C++代码

首先感谢一下那些为我提供帮助的人，主要包括CSDN和洛谷的好心人

制作不易，求支持qwq

---

正文

---

 高精度定义

高精度算法（High Accuracy Algorithm）是处理大数字的数学计算方法。在一般的科学计算中，会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数，高精度算法是用计算机对于超大数据的一种模拟加，减，乘，除，乘方，阶乘，开方等运算。对于非常庞大的数字无法在计算机中正常存储，于是，将这个数字拆开，拆成一位一位的，或者是四位四位的存储到一个数组中， 用一个数组去表示一个数字，这样这个数字就被称为是高精度数。高精度算法就是能处理高精度数各种运算的算法，但又因其特殊性，故从普通数的算法中分离，自成一家。

                                                                                                                            ——百度百科

---

高精度op高精度

高精度加法（高精度加高精度）

普通版

<code>#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;

}

高精度开根低精度 

洛谷P2293

感谢这位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);

}

转自这里

高精度低精度互转

<code>#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;

}

---

结语

求支持！

还是感谢一下那些为我提供帮助的人

此外，还有什么没有嘛？可以告诉我一下，我要是能找到就补充上去