「学習ノート」C++高精度アルゴリズム

高精度アルゴリズムはlong longを解決しても解決できない計算を解決します
 
高精度の記憶は各ビットを単独で記憶し、逆順序で記憶し、配列num[1]はこの数のビットであり、num[2]はこの数の10ビットであり、このように推定される.
 
 
(一)高精度加算
 

#include 
#include 
using namespace std;

struct HugeInt{
	int len;
	int num[100001];
}; 

HugeInt a, b, w;        //w    
char c[100001], d[100001];

void Scan_HugeInt() {   //        
	cin >> c;
	cin >> d;
	a.len = strlen(c); //strlen    
	b.len = strlen(d);
	for(int i=0; i=1; i--) cout << w.num[i]; //          
	cout << endl;
	return 0;
}

 
 
 
(二)高精度減算
 

#include 
#include 
using namespace std;

struct HugeInt {
	int len;
	int num[100001];
};

HugeInt a, b, w;         //w   
char c[100001], d[100001];
bool negative;           //     

void Scan_HugeInt() {    //       
	cin >> c;
	cin >> d;
	if((strlen(c) < strlen(d)) || (strlen(c) == strlen(d) && strcmp(c, d) < 0)) { //              
		negative = true;
		swap(c, d);
	}
	a.len = strlen(c);
	b.len = strlen(d);
	for(int i=0; i=1; i--) cout << w.num[i]; //         
	cout << endl;
	return 0;
}

 
 
 
 
 
(三)高精度乗算
 

#include 
#include 
using namespace std;

struct HugeInt {
	int len;
	int num[100001];
};

HugeInt a, b, w; 
char c[10001], d[10001];

void Scan_HugeInt() {    //       
	cin >> c;
	cin >> d;
	a.len = strlen(c);
	b.len = strlen(d);
	for(int i=0; i=1; i--) cout << w.num[i];
	cout << endl;
	return 0;
}

 
(四)高精度除算
高精細で割ると、各ビットを直接列挙する.
低精細で割った場合、別のシミュレーションを使用するとより高速になります.

Int1000 operator / (const int &b) { //    
	if(*this < Int1000(b)) return Int1000(0);
	Int1000 ans;
	ans.len = len;
	int r = 0;
	for(int i=ans.len; i>=1; i--) {
		r = r * 10 + a[i];
		ans.a[i] = r / b;
		r %= b;
	}
	while(ans.len > 1 && !ans.a[ans.len]) ans.len --;
	return ans;
}
Int1000 operator / (Int1000 b) {
	if(*this < b) return Int1000(0);
	Int1000 ans; ans.len = len - b.len + 1;
	for(int i=ans.len; i>=1; i--) {
		for(int j=1; j<=9; j++) {
			ans.a[i] ++;
			if((*this) < (ans * b)) {
				ans.a[i] --;
				break;
			}
		}
	        if(ans.a[ans.len] == 0) ans.len --;
        }
	while(ans.len > 1 && !ans.a[ans.len]) ans.len --;
	return ans;
}

 
高精度テンプレート:
PS:定数が大きく、慎重に使用
 

const int MAX_SIZE = 1010;

struct Int {
	int len, n[MAX_SIZE];
	void Set(int l) {
		len = l;
		for(int i = 1; i <= len; i ++) n[i] = 0;
	}
	Int(char *s) {
		len = strlen(s);
		for(int i = len - 1; ~i; i --) {
			if(s[i] <= '9' && s[i] >= '0') {
				len = i + 1;
				break;
			}
		}
		for(int i = len; i >= 1; i --) n[i] = s[len - i] - '0';
	}
	Int(long long x = 0) {
		len = 0;
		do {
			n[++ len] = x % 10;
			x /= 10;
		} while(x);
	}
	bool operator < (const Int b) {
		if(len != b.len) return len < b.len;
		for(int i = len; i; i --)
			if(n[i] != b.n[i]) return n[i] < b.n[i];
		return false;
	}
	Int operator + (const Int b) const {
		Int ans; ans.Set(max(len, b.len) + 1);
		for(int i = 1; i <= ans.len; i ++) {
			if(i <= len) ans.n[i] += n[i];
			if(i <= b.len) ans.n[i] += b.n[i];
			ans.n[i + 1] += ans.n[i] / 10;
			ans.n[i] %= 10;
		}
		while(!ans.n[ans.len] && ans.len > 1) ans.len --;
		return ans;
	}
	Int operator - (const Int b) {
		Int ans, a = *(this); ans.Set(len);
		for(int i = 1; i <= ans.len; i ++) {
			if(a.n[i] < b.n[i]) a.n[i + 1] --, a.n[i] += 10;
			ans.n[i] += a.n[i] - (i > b.len ? 0 : b.n[i]);
		}
		while(!ans.n[ans.len] && ans.len > 1) ans.len --;
		return ans;
	}
	Int operator * (Int b) {
		Int ans; ans.Set(len + b.len);
		for(int i = 1; i <= len; i ++) {
			for(int j = 1; j <= b.len; j ++) {
				ans.n[i + j - 1] += n[i] * b.n[j];
				ans.n[i + j] += ans.n[i + j - 1] / 10;
				ans.n[i + j - 1] %= 10;
			}
		}
		while(!ans.n[ans.len] && ans.len > 1) ans.len --;
		return ans;
	}
	Int operator / (const int &b) { //      
     	    if(*this < Int(b)) return Int(0LL);  
     	    Int ans; ans.len = len;  
     	    int r = 0;  
     	    for(int i = ans.len; i; i --) {  
     		r = r * 10 + n[i];  
     		ans.n[i] = r / b;  
          	r %= b;  
        }  
            while(ans.len > 1 && !ans.a[ans.len]) ans.len --;  
            return ans;  
        }  
	Int operator / (const Int b) {
		if((*this) < b) return Int(0LL);
		Int ans; ans.Set(len - b.len + 1);
		for(int i = ans.len; i; i --) {
			for(int j = 1; j <= 9; j ++) {
				ans.n[i] ++;
				if((*this) < (ans * b)) {
					ans.n[i] --;
					break;
				}
			}
		}
		while(ans.len > 1 && !ans.n[ans.len]) ans.len --;
		return ans;
	}
	void print() {
		for(int i = len; i; i --) 
			printf("%d", n[i]);
		printf("
");
	}
};

 
ブラックテクノロジー:2つのlong longが高精度を実現

typedef long long LL;
const LL Base = (LL)1e9;

struct Long {
    LL high, low;
    Long(LL x = 0) : low(x) {high = 0;}
    friend Long operator + (const Long &a, const Long &b) {
        Long c; c.high = a.high + b.high, c.low = a.low + b.low;
        if (c.high >= 0 && c.low >= Base) c.high += c.low / Base, c.low = c.low % Base;
        if (c.high <= 0 && c.low <= -Base) c.high += c.low / Base, c.low = c.low % Base;
        if (c.high > 0 && c.low < 0) c.high --, c.low += Base;
        if (c.high < 0 && c.low >= Base) c.high ++, c.low -= Base;
        return c;
    }
    friend bool operator