CSP-S 复习 ---- 高精度全家桶

CSP-S 复习 ---- 高精度全家桶

#include#define cs constusing namespace std;#define poly vector cs int N = 4e5 + 5;cs double PI = acos(-1.0);struct node{ double x, y; node(double _x = 0, double _y = 0){ x = _x; y = _y; } node operator + (cs node &a){ return node(x + a.x, y + a.y); } node operator - (cs node &a){ return node(x - a.x, y - a.y); } node operator * (cs node &a){ return node(x * a.x - y * a.y, x * a.y + y * a.x); } }f[N], g[N]; int bit, up, rev[N];void init(int len){ bit = 0; up = 1; while(up <= len) up <<= 1, bit++; for(int i = 0; i < up; i++) rev[i] = (rev[i>>1]>>1) | ((i&1) << (bit-1)); }void FFT(node *a, int typ){ for(int i = 0; i < up; i++) if(i < rev[i]) swap(a[i], a[rev[i]]); for(int i = 1; i < up; i <<= 1){ node wn(cos(PI / i), typ * sin(PI / i)); for(int j = 0; j < up; j += (i<<1)){ node w(1, 0); for(int k = 0; k < i; k++, w = w * wn){ node x = a[k+j], y = a[k+j+i] * w; a[k+j] = x + y; a[k+j+i] = x - y; } } }}struct Bignum{ poly a; int flg; // + - #define pb push_back friend Bignum Mul(Bignum A, Bignum B){ Bignum C; int n = A.a.size(), m = B.a.size(); int len = n + m - 1; init(len); for(int i = 0; i < up; i++) f[i] = g[i] = node(0, 0); for(int i = 0; i < n; i++) f[i].x = A.a[i]; for(int i = 0; i < m; i++) g[i].x = B.a[i]; FFT(f, 1); FFT(g, 1); for(int i = 0; i < up; i++) f[i] = f[i] * g[i]; FFT(f, -1); for(int i = 0; i < up; i++){ int v = (int)(f[i].x / up + 0.5); C.a.pb(v); } C.a.resize(len); return C; } friend Bignum operator + (Bignum A, Bignum B){ Bignum C; int len = max(A.a.size(), B.a.size()); A.a.resize(len); B.a.resize(len); C.a.resize(len + 1); for(int i = 0; i < len; i++){ C.a[i] += A.a[i] + B.a[i]; if(C.a[i] >= 10) C.a[i] -= 10, C.a[i + 1]++; } if(!C.a[len]) C.a.resize(len); return C; } friend bool operator == (Bignum A, Bignum B){ if(A.a.size() != B.a.size()) return false; for(int i = A.a.size() - 1; i >= 0; i--){ if(A.a[i] != B.a[i]) return false; } return true; } friend bool operator < (Bignum A, Bignum B){ if(A.a.size() != B.a.size()) return A.a.size() < B.a.size(); for(int i = A.a.size() - 1; i >= 0; i--){ if(A.a[i] != B.a[i]) return A.a[i] < B.a[i]; } } friend Bignum operator - (Bignum A, Bignum B){ Bignum C; if(A == B){ C.a.pb(0); return C;} if(A < B) swap(A, B), C.flg = -1; int len = A.a.size(); C.a.resize(len); B.a.resize(len); for(int i = 0; i < len; i++){ C.a[i] += A.a[i] - B.a[i]; if(C.a[i] < 0) C.a[i] += 10, C.a[i + 1]--; } while(!C.a[C.a.size() - 1]) C.a.pop_back(); return C; } friend Bignum operator * (Bignum A, Bignum B){ Bignum C; int len = A.a.size() + B.a.size(); if(len <= 512){ C.a.resize(len); for(int i = 0; i < A.a.size(); i++){ for(int j = 0; j < B.a.size(); j++){ C.a[i + j] += A.a[i] * B.a[j]; } } } else{ C = Mul(A, B); C.a.resize(len); } for(int i = 0; i < C.a.size(); i++){ if(C.a[i] >= 10){ int k = C.a[i] / 10; C.a[i] -= k * 10; C.a[i + 1] += k; } } if(!C.a[len - 1]) C.a.pop_back(); return C; } friend int operator % (Bignum A, int b){ int nx = 0; for(int i = A.a.size() - 1; i >= 0; i--){ nx = (nx * 10 + A.a[i]) % b; } return nx; } friend Bignum operator / (Bignum A, int b){ Bignum B; int len = A.a.size(), nx = 0; for(int i = len - 1; i >= 0; i--){ nx = nx * 10 + A.a[i]; if(nx >= b){ int k = nx / b; B.a.pb(k); nx -= k * b; } else if(B.a.size()) B.a.pb(0); } reverse(B.a.begin(), B.a.end()); return B; } void read(){ char ch = 0; while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)) a.pb(ch - '0'), ch = getchar(); reverse(a.begin(), a.end()); // 小的位在前面 } void print(){ if(flg == -1) putchar('-'); for(int i = a.size()-1; i >= 0; i--) cout << a[i]; }}A, B; int x;int main(){ A.read(); B.read(); (A + B).print(); puts(""); (A - B).print(); puts(""); (A * B).print(); puts(""); A.read(); scanf("%d", &x); int y = A % x, ans = y; while(y) B.a.push_back(y % 10), y /= 10; A = A - B; (A / x).print(); puts(""); cout << ans << '\n'; return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。