2011
- 题目链接http://noi.openjudge.cn/ch0204/2991/
- 描述
- 已知长度最大为200位的正整数n，请求出2011^n的后四位。
- 输入
- 第一行为一个正整数k，代表有k组数据，k<=200接下来的k行，
每行都有一个正整数n，n的位数<=200 - 输出
- 每一个n的结果为一个整数占一行，若不足4位，去除高位多余的0
- 样例输入
-
3 5 28 792
- 样例输出
-
1051 81 5521
查看
这题用分治来做，另外练习操作符重载
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<string> #include<vector> #include<ios> #define DEBUG(x) cout<<#x<<" = "<<x<<endl using namespace std; const int MAXN=220; struct BigInt{ char digits[MAXN]; int len; BigInt(){ memset(digits,0,sizeof(digits)); len=0; }; bool isOdd() { int n=digits[0]-'0'; return n%2!=0; } friend istream& operator>>(istream & in,BigInt &n) { in>>n.digits; n.len=strlen(n.digits); reverse(n.digits,n.digits+n.len); return in; } friend ostream& operator<<(ostream &out, const BigInt &n) { out<<n.digits; return out; } BigInt half() { BigInt rt; int carry=0; for(int i=len-1;i>=0 ;i-- ){ int v=digits[i]-'0'; rt.digits[i]=(v+carry)/2+'0'; carry=(v+carry)%2*10; } int p=len-1; while(rt.digits[p]=='0'){ if(p!=0) rt.digits[p]='