大数运算

在计算中，如果运算数值超过自带整型的范围，则会溢出。因此在这类计算中，通常把数存放在数组中。进行运算。

1、大数阶乘（相乘）

　　在N!中的计算中首先先计数出N!的位数。设位数为m。则

　　　　pow(10,m-1)<=N!<=pow(10,m)-1<pow(10,m)。　　　　

　　　　m-1<=log10(N)<m

　　　　m=log10(2)+log10(3)...........+log10(N)+1

　　贴上计算代码　

 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 typedef long long ll;
 7 int a[500000];
 8 
 9 void reset(int m){
10     for(int i=0;i<=m;i++)
11         a[i]=0;
12 }
13 
14 void countn(int num,ll t){
15     int k=0;
16     a[0]=1;
17     for(ll i=2;i<=t;i++)
18         for(int j=0;j<num;j++){
19             a[j]*=i;
20             a[j]+=k;
21             k=a[j]/10;
22             a[j]%=10;
23         }
24     for(int i=num-1;i>=0;i--)
25         cout<<a[i];
26     cout<<endl;
27 
28 }
29 
30 int main(){
31     ll t,num=1;
32     double m;
33     while(cin>>t){
34         m=0;
35         for(int i=2;i<=t;i++)
36             m+=log10(i);
37         num=(int)m+1;
38         reset(num);
39         countn(num,t);
40     }
41 
42 
43 }

View Code

　　大数相乘

 1 #include<iostream>
 2 #include<math.h>
 3 #include<string.h>>
 4 using namespace std;
 5 
 6 void reset(int *m,int length){
 7     for(int i=0;i<length;i++)
 8         m[i]=0;
 9 }
10 
11 int main(){
12     string M,N;
13     int m[10000],n[10000];
14     cin>>M;
15     cin>>N;
16     int m_len=M.length();
17     int n_len=N.length();
18     int total=m_len+n_len;
19     int mul[total];
20     for(int i=0;i<m_len;i++){
21         m[i]=M[m_len-1-i]-48;
22     }
23     for(int i=0;i<n_len;i++){
24         n[i]=N[n_len-1-i]-48;
25     }
26 
27     reset(mul,total);
28     for(int i=0;i<n_len;i++){
29         for(int j=0;j<m_len;j++){
30              int index=j+i;
31              mul[index]+=n[i]*m[j];
32              mul[index+1]+=mul[index]/10;
33              mul[index]%=10;
34         }
35     }
36     if(mul[total-1]==0)
37         total--;
38     for(int i=total-1;i>=0;i--)
39         cout<<mul[i];
40     return 0;
41 }

View Code

2、大数相加（相减类似）

　　首先找出俩个数最大的那个，对齐，从个位依次相加。逢10进一，依次类推。

　　大数相加

 1 #include<iostream>
 2 #include<string.h>
 3 using namespace std;
 4 
 5 int main(){
 6     string M,N;
 7     int m[10000],n[10000];
 8     cin>>M;
 9     cin>>N;
10     int m_len=M.length();
11     int n_len=N.length();
12     int total=m_len>n_len?m_len:n_len;
13     memset(m,0,total);
14     memset(n,0,total);
15     for(int i=0;i<m_len;i++){
16         m[i]=M[m_len-1-i]-48;
17     }
18     for(int i=0;i<n_len;i++){
19         n[i]=N[n_len-1-i]-48;
20     }
21     int carry=0;
22     for(int i=0;i<total;i++){
23         m[i]=m[i]+n[i]+carry;
24         if(m[i]>9){
25             m[i]%=10;
26             carry=1;
27         }
28         else{
29             carry=0;
30         }
31     }
32     if(carry==1)
33         cout<<"1";
34         for(int i=total-1;i>=0;i--){
35             cout<<m[i];
36     }
37 }

View Code

　　大数相减

 1 #include<iostream>
 2 #include<string.h>
 3 using namespace std;
 4 
 5 void printSub(int *a,int *b,int length,bool isBig){
 6     int carry=0;
 7     for(int i=0;i<length;i++){
 8         if(a[i]<b[i]+carry){
 9             a[i]=a[i]+10-b[i]-carry;
10             carry=1;
11         }
12         else{
13             a[i]=a[i]-b[i]-carry;
14             carry=0;
15         }
16     }
17     if(!isBig)
18     cout<<"-";
19     if(a[length-1]==0)
20         length--;
21     for(int i=length-1;i>=0;i--){
22         cout<<a[i];
23     }
24 }
25 
26 int main(){
27     string M,N;
28     int m[10000],n[10000];
29     cin>>M;
30     cin>>N;
31     int m_len=M.length();
32     int n_len=N.length();
33     bool isBig=m_len>=n_len?true:false;
34     int total=isBig?m_len:n_len;
35     memset(m,0,total);
36     memset(n,0,total);
37      for(int i=0;i<m_len;i++){
38         m[i]=M[m_len-1-i]-48;
39     }
40     for(int i=0;i<n_len;i++){
41         n[i]=N[n_len-1-i]-48;
42     }
43     if(isBig)
44         printSub(m,n,total,isBig);
45     else
46         printSub(n,m,total,isBig);
47     return 0;
48 }

View Code

3、大数相除

　　一般大数相除中，常见的思路是

　　例如8888/300

　　300*10=3000

　　3000*2=6000

　　依次类推，则算出商为29，余数为188，可以考虑采取二分法进行判断，获取最大的整数倍数分析。

　　如果除数为能用int表示的变量，则从首位依次类推，下面列出例子：

 1 #include<iostream>
 2 #include<math.h>
 3 #include<string.h>
 4 using namespace std;
 5 
 6 int main(){
 7     int d,remainder;
 8     string m;
 9     cin>>m;
10     cin>>d;
11     int m_len=m.length();
12     int arr[m_len],quo[m_len];
13     for(int i=0;i<m_len;i++){
14         arr[i]=m[i]-48;
15         }
16     int divisor=0,index=0,q_index=0;
17     while(index<m_len){
18         divisor=divisor*10+arr[index];
19         if(divisor<d){
20             quo[q_index]=0;
21         }
22         else{
23             quo[q_index]=divisor/d;
24             divisor%=d;
25         }
26         index++;
27         q_index++;
28     }
29     for(int i=0;i<q_index;i++)
30     {
31         if(quo[i]!=0){
32             index=i;
33             break;
34         }
35     }
36     if(index==q_index-1)
37         cout<<"0";
38     else
39         for(int i=index;i<q_index;i++)
40             cout<<quo[i];
41     return 0;
42 }

View Code