高精度
普通的long long只能存64位，可64位以上的數怎么存盤呢，又怎么運算呢，這里就引入高精度，
這里博主用一個結構體來完成，用結構體有個好處，如有一些題需要用高精，我們可以像平常一樣處理；
存盤
struct bignum{
ll n[N>>2];
bool op=0;//1 +，0 -
const ll mod=1e8;
這里作者壓8位存盤，即陣列的每個位置都存一個八位數，且是倒序存盤，并用0這個位置存盤陣列長度，op是這個數的符號，1為正，0為負，mod是在進位是用到的，壓一位時就除以10，壓8位是就除以1e8（意思是10^8)，舉個例子：
1234597812345678123
0 3
1 45678123
2 45978123
3 123//這里的0、1、2、3即指陣列的零號位置、一號位置，二號位置、三號位置
輸出
void out()
{
if(!op&&(n[1]||n[0]!=1)) cout<<"-",op=0;
printf("%lld",n[n[0]]);
for(int i=n[0]-1;i>0;i--) printf("%08lld",n[i]);
cout<<endl;
}
如果op是0（！op) 并且n[1] 不為0或n[0]不為1，則輸出負號，排除了符號為正和數字為0的情況，然后輸出n[n[0]]，也就是最高位，其余按8位輸出，不滿八位補0，
因為是倒序存入，所以是倒序輸出，而倒序的原因是因為方便進行運算，
復制（這里相當于’=‘）
void cpy(bignum a)
{
for(int i=a.n[0];i>n[0];i--) n[i]=0;
for(int i=0;i<=a.n[0];i++) n[i]=a.n[i];
op=a.op;
}
這里比較好理解，第一個for實作了把其余的元素清0，第二個for實作了復制，然后把符號也復制過來，
比較
int cmp(bignum a)
{
if(n[0]>a.n[0]) return 1;
if(n[0]<a.n[0]) return -1;
for(int i=n[0];i;i--)
{
if(n[i]>a.n[i]) return 1;
if(n[i]<a.n[i]) return -1;
}
return 0;
}
這里是一個比較函式，注意，這里比較的是絕對值，所以并沒有符號的比較，總體思路是先比較長度，在比較每一位（倒序比較），把*this與a作比較，>a回傳1，<a回傳-1，=a回傳0；
輸入
void init()
{
string ss;
cin>>ss;
if(ss[0]=='-') ss[0]='0',op=0;
int len=ss.length();
for(int i=len-1;i>=0;i-=8)
{
ll pw=1;
for(int j=i;j>i-8&&j>=0;j--)
{
n[n[0]]+=(ss[j]^48)*pw;
pw=(pw<<3)+(pw<<1);
}
++n[0];
}
n[0]--;
}
定義一個陣列，cin輸入，然后判斷開頭是否為負號，如果是，則把原來負號在的位置改成‘0’，并讓op=0，
接下來用len來存盤ss的長，倒序存盤fori 用來列舉開始的位置，而forj表示從i開始，倒序訪問往后8個字符，并把該字符轉化成對應位置的數字，pw在這里的作用是讓數字對應好他的位數，pw=(pw<<3)+(pw<<1)就等價于pw*=10；處理完后n0++, 最后n0--
因為有建構式的存在，n0的初始值為1，所有函式最后n0會比正常值多1
交換
void sp(bignum& b)
{
bignum c;
c.cpy(*this);
this->cpy(b);
b.cpy(c);
}
交換函式，沒什么好說的，主要說一下this，this是一個指標，指向自己，當需要參考函式時，用this->函式（），就相當于bignum c；c.函式（），
有興趣的讀者請自行查閱
建構式
bignum ()
{
memset(n,0,sizeof(n));
op=1;
n[0]=1;
}
建構式，在定義時被參考，也就是說，你在定義了bignum a;那么同時a.n被清零，a.op=1，a.n[0]=1
運算——加法
bignum operator + (bignum b)// a>0 b>0
{
bignum c;
if(op==b.op) c.op=op;
else
{
if(op==1)
{
b.op=1;
return *this-b;
}
else
{
op=1;
return b-*this;
}
}
c.n[0]=max(n[0],b.n[0])+1;
for(int i=1;i<=c.n[0];i++)
{
c.n[i]+=n[i]+b.n[i];
if(c.n[i]>=mod) c.n[i]-=mod,c.n[i+1]++;
}
while(!c.n[c.n[0]]&&c.n[0]>1) c.n[0]--;
return c;
}
這里使用了多載運算子operator，顧名思義，這個賦予了‘+’另外的含義，因為它被定義在結構體bignum中，所以只有是bignum型別的，才支持這種‘+’，其他型別，比如說int，該怎么樣還怎么樣，
定義一個結構體c，使得c=this+b，如果op和b的op相等的話，c的op也等于它們，否則，改變符號，改之前的正數減去負數，
這里不用擔心改完符號后兩數的大小，在‘-’中會專門處理這件事，
其余比較簡單，加完進位，去前導0；
運算——減法
bignum operator - (bignum b) //a>b>0
{
bignum c,d;
d.cpy(*this);
if(op!=b.op)
{
b.op^=1;
return *this+b;
}
else c.op=op;
if(this->cmp(b)==-1)
{
this->sp(b);
c.op^=1;
}
c.n[0]=max(n[0],b.n[0]);
for(int i=1;i<=c.n[0];i++)
{
c.n[i]+=n[i]-b.n[i];
if(c.n[i]<0) c.n[i]+=mod,c.n[i+1]--;
}
while(!c.n[c.n[0]]&&c.n[0]>1) c.n[0]--;
this->cpy(d);
return c;
}
這里有兩個結構體，c和d，c的作用和‘+’一樣，而d的作用是暫時的存盤一下this，原因就是在我們參考sp時會改變this的的值，那么最后我們要把它改回來，
這里如果this與b符號不同，就把b的符號改成另一個，即1改0，0改1，這里巧妙的用到'^'，0 ^0=1，0 ^ 1=1，0 ^1=1，1 ^1=0，否則c的op就和他們一樣，
如果*this比b小，交換一下兩邊的值，c的符號取相反，
接下來就是減法，減去，借位，除去前導0，
運算——乘法
bignum operator * (bignum b)
{
bignum c;
c.n[0]=n[0]+b.n[0];
for(int i=1;i<=n[0];i++)
{
for(int j=1;j<=b.n[0];j++)
{
c.n[i+j-1]+=n[i]*b.n[j];
if(c.n[i+j-1]>=mod) c.n[i+j]+=c.n[i+j-1]/mod,c.n[i+j-1]%=mod;
}
}
while(!c.n[c.n[0]]&&c.n[0]>1) c.n[0]--;
if(op!=b.op) c.op=0;
return c;
}
乘法主要模擬了乘法豎式，沒有什么好說的，如果符號不一樣，c的符號就取負，
當this為i，b為j時，c相對應的是i+j-1
除法
那么在看除法之前我們需要先看一下兩個操作，左移一位（乘2），右移一位（除以2）
左移一位
void ly()
{
++n[0];
for(int i=1;i<=n[0];i++)
{
n[i]<<=1;
if(n[i-1]>=mod) n[i-1]-=mod,++n[i];
}
if(!n[n[0]]&&n[0]>1) --n[0];
}
首先先假設*2后有進位，然后對陣列每8位進行左移一位，處理進位，最后去除前導0，
這里倒序和正序沒什么區別
右移一位
void ry()
{
for(int i=n[0];i;--i)
{
if((n[i]&1)&&i>1) n[i-1]+=mod;
n[i]>>=1;
}
if(!n[n[0]]&&n[0]>1) --n[0];
}
這里略有一些麻煩，for回圈陳述句1的意思是：如果n[i]的二進制的最后一位是1（n[i]&1）且 i-1>0(i>1) ，那么在這種情況下，ni是一個奇數，右移一位是除以二，若是奇數直接除以2的話會少去余數1，，所以把ni減1，ni-1加上mod，然后右移一位，最后去除前導0
位運算比平常的乘除快
然后我們來看一下除法
運算——除法
bignum operator / (bignum b)
{
bignum cp,lt,c,d;
d.cpy(*this);
if(op!=b.op) lt.op=0;
cp.n[1]=1;
while(this->cmp(b)!=-1) b.ly(),cp.ly();
while(cp.n[1]||cp.n[0]>1)
{
if(this->cmp(b)!=-1)
{
c.cpy(*this-b);
this->cpy(c);
c.cpy(lt+cp);
lt.cpy(c);
}
b.ry();
cp.ry();
}
lt.out();
lt.cpy(*this);
this->cpy(d);
return lt;
}
因為這里會用到減法，所以仍然由d來存盤this，這里又定義了cp與lt,我們先往后看，然后是符號處理，如果this比b小，那b和ly就一直乘二，如果cp1里面有值，或者cp0大于1，則繼續回圈，如果this比b大，則c等于this減b，然后把c復制到this里，相當于this-=b；
下面同樣，lt+=cp；然后b和cp各除以2；
這一切結束后，lt里面放的是商，*this里面是余數，剩下的部分依個人情況而定，
那么這么做的原理是什么？我給大家講講原理，并模擬一下我們知道，
二的倍數和1可以組成任何數,
這是由于在二進制下，1是第一位；2是第二位，4是第三位......
例如：
43210
11001
(25)10=(11001)2=2^4+2^3+2^0=16+8+1=25
N=n*a+b;
N-n*a=b;
127=3*42+1;
127-3*42=1;
b=3*2*2*2*2*2*2=192;
cp=2*2*2*2*2*2=(64)10=(1000000)2
127<196
b>>=1,cp>>=1
b=96 cp=(100000)2
127>96
N-=b=31
b>>=1,cp>>=1
b=48 cp=(10000)2 lt=(100000)2
31<48
b>>=1,cp>>=1
b=24 cp=(1000)2
31>24
N-=b=7
b>>=1,cp>>=1
b=12 cp=(100)2 lt=(101000)2
7<12
b>>=1,cp>>=1
b=6 cp=(10)2
7>6
N-=b=1
b>>=1,cp>>=1
b=3 cp=(1)2 lt=(101010)2
1<3
b>>=1,cp>>=1
b=1 cp=(0)2
end
lt=(101010)2=(42)10
所以，cp其實模擬的是商的二進制的每一位！看看哪些2的倍數加起來是a，最后剩下的就是余數，
()2指的是2進制下的數，()10同理
最后附上完整代碼
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<deque>
#define dd double
#define ll long long
#define N 10010
using namespace std;
struct bignum{
ll n[N>>2];
bool op=0;//1 +,0 -
const ll mod=1e8;
void out()
{
if(!op&&(n[1]||n[0]!=1)) cout<<"-",op=0;
printf("%lld",n[n[0]]);
for(int i=n[0]-1;i>0;i--) printf("%08lld",n[i]);
cout<<endl;
}//over
void ry()
{
for(int i=n[0];i;--i)
{
if((n[i]&1)&&i>1) n[i-1]+=mod;
n[i]>>=1;
}
if(!n[n[0]]&&n[0]>1) --n[0];
}
void ly()
{
++n[0];
for(int i=1;i<=n[0];i++)
{
n[i]<<=1;
if(n[i-1]>=mod) n[i-1]-=mod,++n[i];
}
if(!n[n[0]]&&n[0]>1) --n[0];
}
void cpy(bignum a)
{
for(int i=a.n[0];i>n[0];i--) n[i]=0;
for(int i=0;i<=a.n[0];i++) n[i]=a.n[i];
op=a.op;
}
int cmp(bignum a)
{
if(n[0]>a.n[0]) return 1;
if(n[0]<a.n[0]) return -1;
for(int i=n[0];i;i--)
{
if(n[i]>a.n[i]) return 1;
if(n[i]<a.n[i]) return -1;
}
return 0;
}
void init()
{
string ss;
cin>>ss;
if(ss[0]=='-') ss[0]='0',op=0;
int len=ss.length();
for(int i=len-1;i>=0;i-=8)
{
ll pw=1;
for(int j=i;j>i-8&&j>=0;j--)
{
n[n[0]]+=(ss[j]^48)*pw;
pw=(pw<<3)+(pw<<1);
}
++n[0];
}
n[0]--;
}
void sp(bignum& b)
{
bignum c;
c.cpy(*this);
this->cpy(b);
b.cpy(c);
}
bignum ()
{
memset(n,0,sizeof(n));
op=1;
n[0]=1;
}
bignum operator + (bignum b)// a>0 b>0
{
bignum c;
if(op==b.op) c.op=op;
else
{
if(op==1)
{
b.op=1;
return *this-b;
}
else
{
op=1;
return b-*this;
}
}
c.n[0]=max(n[0],b.n[0])+1;
for(int i=1;i<=c.n[0];i++)
{
c.n[i]+=n[i]+b.n[i];
if(c.n[i]>=mod) c.n[i]-=mod,c.n[i+1]++;
}
while(!c.n[c.n[0]]&&c.n[0]>1) c.n[0]--;
return c;
}
bignum operator - (bignum b) //a>b>0
{
bignum c,d;
d.cpy(*this);
if(op!=b.op)
{
b.op^=1;
return *this+b;
}
else c.op=op;
if(this->cmp(b)==-1)
{
this->sp(b);
c.op^=1;
}
c.n[0]=max(n[0],b.n[0]);
for(int i=1;i<=c.n[0];i++)
{
c.n[i]+=n[i]-b.n[i];
if(c.n[i]<0) c.n[i]+=mod,c.n[i+1]--;
}
while(!c.n[c.n[0]]&&c.n[0]>1) c.n[0]--;
this->cpy(d);
return c;
}
bignum operator * (bignum b)
{
bignum c;
c.n[0]=n[0]+b.n[0];
for(int i=1;i<=n[0];i++)
{
for(int j=1;j<=b.n[0];j++)
{
c.n[i+j-1]+=n[i]*b.n[j];
if(c.n[i+j-1]>=mod) c.n[i+j]+=c.n[i+j-1]/mod,c.n[i+j-1]%=mod;
}
}
while(!c.n[c.n[0]]&&c.n[0]>1) c.n[0]--;
if(op!=b.op) c.op=0;
return c;
}
bignum operator / (bignum b)
{
bignum cp,lt,c,d;
d.cpy(*this);
if(op!=b.op) lt.op=0;
cp.n[1]=1;
while(this->cmp(b)!=-1) b.ly(),cp.ly();
while(cp.n[1]||cp.n[0]>1)
{
if(this->cmp(b)!=-1)
{
c.cpy(*this-b);
this->cpy(c);
c.cpy(lt+cp);
lt.cpy(c);
}
b.ry();
cp.ry();
}
lt.out();
lt.cpy(*this);
this->cpy(d);
return lt;
}
};
int main()
{
bignum a,b,c;
a.init();
b.init();
cout<<endl;
cout<<endl;
c.cpy(a+b);
c.out();
c.cpy(a-b);
c.out();
c.cpy(a*b);
c.out();
c.cpy(a/b);
c.out();
}
這個代碼有一個漏洞，如果存的數位數很大，大約有2000位這么大，會出現在輸入時輸入不完的問題，大概是到了string或cin的極限了吧，看看以后有機會改一下，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/51492.html
標籤：其他
下一篇：2019 ICPC Asia Yinchuan Regional G. Pot!!（線段樹 區間更新 區間查詢）