题目:
使用求和公式求1到N的累加和大家都会,但是如果把N值变大呢,比如100位的整数,那该怎么求?
输入格式:
输入在一行中给出1个位数不超过100位的整数N。
输出格式:
对每一组输入,在一行中输出1+2+3+……+N的值。
输入样例:
输出样例:
思路:
由于本题的位数过大,所以在高精度计算累加和时需要使用等差数列的求和公式(a1+an)*n/2,通过模拟列竖式计算等手算操作编写高精度运算函数求符合题目输入的上式即可。代码如下:
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
| #include <bits/stdc++.h>
using namespace std;
vector<int> N;
vector<int> add(vector<int> &A,vector<int> &B) { if(A.size()<B.size()) return add(B,A); vector<int> C; int t=0; for(int i=0;i<A.size();i++) { t+=A[i]; if(i<B.size()) t+=B[i]; C.push_back(t%10); t/=10; } if(t) C.push_back(t); return C; }
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]; } } int t=0; for(int i=0;i<C.size();i++) { t+=C[i]; C[i]=t%10; t/=10; } while(C.size()>1&&C.back()==0) C.pop_back(); return C; }
vector<int> div(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(); return C; }
int main() { string str_N; cin>>str_N; for(int i=str_N.length()-1;i>=0;i--) N.push_back(str_N[i]-'0'); vector<int> one; one.push_back(1); auto tmp=add(one,N); tmp=mul(tmp,N); int surplus; auto res=div(tmp,2,surplus); for(int i=res.size()-1;i>=0;i--) cout<<res[i]; }
|