The Chosen One+高精度

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int maxn = 1000;
  4 struct bign{
  5     int d[maxn], len;
  6     void clean() { while(len > 1 && !d[len-1]) len--; }
  7     bign()          { memset(d, 0, sizeof(d)); len = 1; }
  8     bign(int num)   { *this = num; }
  9     bign(char* num) { *this = num; }
 10     bign operator = (const char* num){
 11         memset(d, 0, sizeof(d)); len = strlen(num);
 12         for(int i = 0; i < len; i++) d[i] = num[len-1-i] - '0';
 13         clean();
 14         return *this;
 15     }
 16     bign operator = (int num){
 17         char s[20]; sprintf(s, "%d", num);
 18         *this = s;
 19         return *this;
 20     }
 21     bign operator + (const bign& b){
 22         bign c = *this; int i;
 23         for (i = 0; i < b.len; i++){
 24             c.d[i] += b.d[i];
 25             if (c.d[i] > 9) c.d[i]%=10, c.d[i+1]++;
 26         }
 27         while (c.d[i] > 9) c.d[i++]%=10, c.d[i]++;
 28         c.len = max(len, b.len);
 29         if (c.d[i] && c.len <= i) c.len = i+1;
 30         return c;
 31     }
 32     bign operator - (const bign& b){
 33         bign c = *this; int i;
 34         for (i = 0; i < b.len; i++){
 35             c.d[i] -= b.d[i];
 36             if (c.d[i] < 0) c.d[i]+=10, c.d[i+1]--;
 37         }
 38         while (c.d[i] < 0) c.d[i++]+=10, c.d[i]--;
 39         c.clean();
 40         return c;
 41     }
 42     bign operator * (const bign& b)const{
 43         int i, j; bign c; c.len = len + b.len;
 44         for(j = 0; j < b.len; j++) for(i = 0; i < len; i++)
 45             c.d[i+j] += d[i] * b.d[j];
 46         for(i = 0; i < c.len-1; i++)
 47             c.d[i+1] += c.d[i]/10, c.d[i] %= 10;
 48         c.clean();
 49         return c;
 50     }
 51     bign operator / (const bign& b){
 52         int i, j;
 53         bign c = *this, a = 0;
 54         for (i = len - 1; i >= 0; i--)
 55         {
 56             a = a*10 + d[i];
 57             for (j = 0; j < 10; j++) if (a < b*(j+1)) break;
 58             c.d[i] = j;
 59             a = a - b*j;
 60         }
 61         c.clean();
 62         return c;
 63     }
 64     bign operator % (const bign& b){
 65         int i, j;
 66         bign a = 0;
 67         for (i = len - 1; i >= 0; i--)
 68         {
 69             a = a*10 + d[i];
 70             for (j = 0; j < 10; j++) if (a < b*(j+1)) break;
 71             a = a - b*j;
 72         }
 73         return a;
 74     }
 75     bign operator += (const bign& b){
 76         *this = *this + b;
 77         return *this;
 78     }
 79 
 80     bool operator <(const bign& b) const{
 81         if(len != b.len) return len < b.len;
 82         for(int i = len-1; i >= 0; i--)
 83             if(d[i] != b.d[i]) return d[i] < b.d[i];
 84         return false;
 85     }
 86     bool operator >(const bign& b) const{return b < *this;}
 87     bool operator<=(const bign& b) const{return !(b < *this);}
 88     bool operator>=(const bign& b) const{return !(*this < b);}
 89     bool operator!=(const bign& b) const{return b < *this || *this < b;}
 90     bool operator==(const bign& b) const{return !(b < *this) && !(b > *this);}
 91     string str() const{
 92         char s[maxn]={};
 93         for(int i = 0; i < len; i++) s[len-1-i] = d[i]+'0';
 94         return s;
 95     }
 96 };
 97 istream& operator >> (istream& in, bign& x)
 98 {
 99     string s;
100     in >> s;
101     x = s.c_str();
102     return in;
103 }
104 ostream& operator << (ostream& out, const bign& x)
105 {
106     out << x.str();
107     return out;
108 }
109 int main()
110 {
111     int TTT;
112     cin>>TTT;
113     while(TTT--)
114     {
115         bign a,b,c;
116         c=2;
117         cin>>a;
118         b=1;
119         while(b<a) b=b*c;
120         if(b==a) cout<<b<<endl;
121         else{
122             b=b/c;
123             cout<<b<<endl;
124         }
125     }
126     return 0;
127 }