yuhaoran666 @ 2022-05-21 23:05:24
#include<bits/stdc++.h>
using namespace std;
// ------------------------------ superint ------------------------------
#define MAX 5000
struct superint {
short num[MAX];
superint & operator = (const char*);
superint & operator = (int);
superint();
superint(int);
bool operator > (const superint &) const;
bool operator < (const superint &) const;
bool operator <= (const superint &) const;
bool operator >= (const superint &) const;
bool operator != (const superint &) const;
bool operator == (const superint &) const;
superint operator + (const superint &) const;
superint operator - (const superint &) const;
superint operator * (const superint &) const;
superint operator / (const superint &) const;
superint operator % (const superint &) const;
superint operator += (const superint &);
superint operator -= (const superint &);
superint operator *= (const superint &);
superint operator /= (const superint &);
superint operator %= (const superint &);
void pow(superint n) {
superint ret, i;
i = 1;
ret = 1;
for (; i <= n; i += 1) ret *= *this;
*this = ret;
}
};
superint & superint::operator = (const char* c) {
memset(num, 0, sizeof(num));
int n = strlen(c), j = 1, k = 1;
for (int i = 1; i <= n; i ++ ) {
if (k == 10000) j++, k = 1;
num[j] += k * (c[n - i] - '0');
k *= 10;
}
num[0] = j;
return *this;
}
superint & superint::operator = (int a) {
char s[MAX];
sprintf(s, "%d", a);
return *this = s;
}
superint::superint() {
memset(num, 0, sizeof(num));
num[0] = 1;
}
superint::superint(int n) {
*this = n;
}
bool superint::operator > (const superint &b) const {
if (num[0] != b.num[0]) return num[0] > b.num[0];
for (int i = num[0]; i >= 1; i--) {
if (num[i] != b.num[i]) {
return (num[i] > b.num[i]);
}
}
return false;
}
bool superint::operator < (const superint &b) const {
return b > *this;
}
bool superint::operator <= (const superint &b) const {
return !(*this > b);
}
bool superint::operator >= (const superint &b) const {
return !(b > *this);
}
bool superint::operator != (const superint &b) const {
return (b > *this) || (*this > b);
}
bool superint::operator == (const superint &b) const {
return !(b > *this) && !(*this > b);
}
superint superint::operator + (const superint &b) const {
superint c;
c.num[0] = max(num[0], b.num[0]);
for (int i = 1; i <= c.num[0]; i++) {
c.num[i] += num[i] + b.num[i];
if (c.num[i] >= 10000) {
c.num[i] -= 10000;
c.num[i + 1]++;
}
}
if (c.num[c.num[0] + 1] > 0) c.num[0]++;
return c;
}
superint superint::operator - (const superint &b) const {
superint c;
c.num[0] = num[0];
for (int i = 1; i <= c.num[0]; i++) {
c.num[i] += num[i] - b.num[i];
if (c.num[i] < 0) {
c.num[i] += 10000;
c.num[i + 1]--;
}
}
while (c.num[c.num[0]] == 0 && c.num[0] > 1) c.num[0]--;
return c;
}
superint superint::operator += (const superint &b) {
return *this = *this + b;
}
superint superint::operator -= (const superint &b) {
return *this = *this - b;
}
superint superint::operator * (const superint &b) const {
superint c;
c.num[0] = num[0] + b.num[0] + 1;
for (int i = 1; i <= num[0]; i++) {
for (int j = 1; j <= b.num[0]; j++) {
c.num[i + j - 1] += num[i] * b.num[j];
c.num[i + j] += c.num[i + j - 1] / 10000;
c.num[i + j - 1] %= 10000;
}
}
while (c.num[c.num[0]] == 0 && c.num[0] > 1) c.num[0]--;
return c;
}
superint superint::operator *= (const superint &b) {
return *this = *this*b;
}
superint superint::operator / (const superint &b) const {
superint c, d;
c.num[0] = num[0] + b.num[0] + 1;
d.num[0] = 0;
for (int i = num[0]; i >= 1; i--) {
memmove(d.num + 2, d.num + 1, sizeof(d.num) - sizeof(int) * 2);
d.num[0]++;
d.num[1] = num[i];
int left = 0, right = 9999, mid;
while (left < right) {
mid = (left + right) / 2;
if (b * superint(mid) <= d) left = mid + 1;
else right = mid;
}
c.num[i] = right - 1;
d = d - b * superint(right - 1);
}
while (c.num[c.num[0]] == 0 && c.num[0] > 1) c.num[0]--;
return c;
}
superint superint::operator % (const superint &b) const {
superint c, d;
c.num[0] = num[0] + b.num[0] + 1;
d.num[0] = 0;
for (int i = num[0]; i >= 1; i--) {
memmove(d.num + 2, d.num + 1, sizeof(d.num) - sizeof(int) * 2);
d.num[0]++;
d.num[1] = num[i];
int left = 0, right = 9999, mid;
while (left < right) {
mid = (left + right) / 2;
if (b * superint(mid) <= d) left = mid + 1;
else right = mid;
}
c.num[i] = right - 1;
d =d - b * superint(right - 1);
}
while (c.num[c.num[0]] == 0 && c.num[0] > 1) c.num[0]--;
return d;
}
superint superint::operator /= (const superint &b) {
return *this = *this / b;
}
superint superint::operator %= (const superint &b) {
return *this = *this % b;
}
ostream & operator << (ostream &out, superint &n) {
stringstream st1;
st1 << n.num[n.num[0]];
string s1;
st1 >> s1;
cout << n.num[0] * 4 - 4 + s1.length() << endl;
// ---------------------------------------
stringstream st;
for (int i = 125; i >= 1; i--) {
st.width(4);
st.fill('0');
st << n.num[i];
}
string s;
st >> s;
int l = s.length();
for (int i = 0; i < l; i += 50) {
for (int j = i; j <= i + 49; j++) cout << s[j];
cout << endl;
}
return out;
}
istream & operator >> (istream &in, superint &n) {
char s[MAX];
in >> s;
n = s;
return in;
}
// ------------------------------ end ------------------------------
// 主函数
superint p;
int main() {
cin >> p;
if (p <= 20000);
else if (p <= 1000000) {
#undef MAX
#define MAX 500000
}
else {
#undef MAX
#define MAX 775000
}
superint num, sum;
num = 2;
num.pow(p);
num -= 1;
cout << num;
return 0;
}
by fuxiao @ 2022-05-21 23:09:12
我不知道是你写的深奥还是我蒟蒻,总之看不懂
by PassName @ 2022-05-22 00:07:07
@yuhaoran666 想superint
,ae86快读
,自定义函数库
这些操作多与你来说不要乱用,首先,在考场上这些东西你拿不出来,其次,有的时候高级的快读不如正经的快读快写甚至于cin
好使,有的时候画蛇添足反而会错掉。之后就是这个题,你自己hack一个数据,你会发现,当输入的数大于9000
时,你这个就废了,自习看看吧
by yuhaoran666 @ 2022-05-22 00:18:35
@单南松 这题就是高精
by PassName @ 2022-05-22 00:19:32
@yuhaoran666 对,但是这道题不能superint
,老师怎么教怎么来
by yuhaoran666 @ 2022-05-22 00:44:24
@单南松 这道题需要用到superint
里面的很多函数和操作符,但是数据一大就会TLE
,但是int
,long long
,__int128
精度都不够。
by yuhaoran666 @ 2022-05-22 00:48:53
高精是模拟出来的,永远不如int
longlong
快。