50求助

P1045 [NOIP2003 普及组] 麦森数

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 想superintae86快读自定义函数库这些操作多与你来说不要乱用,首先,在考场上这些东西你拿不出来,其次,有的时候高级的快读不如正经的快读快写甚至于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快。


|