记录编号	569070	评测结果	AAAAAAAAAA
题目名称	[NOIP 2003]麦森数	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	2.614 s
提交时间	2022-02-16 13:01:00	内存使用	5.74 MiB

#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#define OPEN(_x) freopen(#_x".in", "r", stdin); freopen(#_x".out", "w", stdout)
#define ABS(_x) ((_x)<0?(-(_x)):(_x))
#define MAX(_a, _b) ((_a)<(_b)?(_b):(_a))
#define MIN(_a, _b) ((_a)>(_b)?(_b):(_a))
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

namespace IO{
    template<typename T>
    inline T read() {
        T ret=0, sig=1; char ch=0;
        while(ch<'0'||ch>'9') { if(ch=='-') sig=-1; ch=getchar(); }
        while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); }
        return ret*sig;
    }
    template<typename T>
    inline void read(T &x) {
        T ret=0, sig=1; char ch=0;
        while(ch<'0'||ch>'9') { if(ch=='-') sig=-1; ch=getchar(); }
        while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); }
        x = ret*sig;
    }
    template<typename T>
    inline void write(T x) {
        if(x<0) putchar('-'), x=-x;
        T stk[100], tt=0;
        do stk[tt++]=x%10, x/=10; while(x);
        while(tt) putchar(stk[--tt]+'0');
    }
};

int n;

vector<int> res = {2};

inline vector<int> calc1(vector<int> &num1, vector<int> &num2) {
    vector<int> ret;
    int t = 0;
    for(register int i = 0; i<num1.size() || i<num2.size() || t; ++i) {
        if(i<num1.size()) t += num1[i];
        if(i<num2.size()) t += num2[i];
        ret.push_back(t % 10);
        t /= 10;
    }
    return ret;
}

inline vector<int> calc2(vector<int> &num1, int num2) {
    vector<int> ret;
    int t = 0;
    for(register int i = 0; i<MIN(num1.size(), 500) || t; ++i) {
        if(i<MIN(num1.size(), 500)) t += num1[i] * num2;
        ret.push_back(t % 10);
        t /= 10;
    }
    while(ret.size() > 1 && !ret.back()) ret.pop_back();
    return ret;
}

inline vector<int> calc2(vector<int> &num1, vector<int> &num2) {
    vector<int> ret = {0};
    for(register int i = MIN(num2.size(), 500); i>=0; --i) {
        ret = calc2(ret, 10);
        auto tmp = calc2(num1, num2[i]);
        ret = calc1(ret, tmp);
    }
    return ret;
}

inline void output() {
    int pos = 0, now = MIN(500, res.size())-1;
    if(res.size() < 500) {
        int remain = 500-res.size();
        while(remain >= 50) {
            remain -= 50;
            for(register int i = 1; i<=50; ++i) putchar(48);
            puts("");
        }
        pos = 50-remain;
        for(register int i = 1; i<=remain; ++i) putchar(48);
        for(register int i = 0; i<pos; ++i) putchar(res[now--]+48);
        puts("");
    }
    while(now >= 50) {
        for(register int i = 1; i<=50; ++i) putchar(res[now--]+48);
        puts("");
    }
    for(register int i = now; i>0; --i) putchar(res[i]+48);
    putchar(res.front()+47);
}

int main() {
    OPEN(mason);
    IO::read(n);
    double lg = 0.30103;
    IO::write((int)ceil(lg*n));
    puts("");
    vector<int> ans = {1};
    while(n) {
        if(n & 1) ans = calc2(ans, res);
        res = calc2(res, res);
        n >>= 1;
    }
    res = ans;
    output();
    return 0;
}