cgxd @ 2024-07-23 16:40:41
#include<bits/stdc++.h>
using namespace std;
int n;
string ans;
unordered_map<string, unordered_map<string, string>> m;
string operator+(string s1, string s2){
if(s1.size() < s2.size())
swap(s1, s2);
if(s2 == "0")
return s1;
reverse(s1.begin(), s1.end());
reverse(s2.begin(), s2.end());
s2.resize(s1.size(), '0');
s1.push_back('0');
for(size_t i = 0; i < s2.size(); ++i){
s1[i] += s2[i] - '0';
if(s1[i] > '9'){
s1[i] -= 10;
++s1[i + 1];
}
}while(s1.back() == '0')
s1.pop_back();
if(s1.empty())
return "0";
reverse(s1.begin(), s1.end());
return s1;
}string operator*(string s1, string s2){
if(s1 == "0" or s2 == "0")
return "0";
if(s2 == "10"){
s1.push_back('0');
return s1;
}if(m.count(s1) and m[s1].count(s2))
return m[s1][s2];
if(s1.size() == 1 and s2.size() == 1)
return m[s1][s2] = to_string((s1[0] - '0') * (s2[0] - '0'));
string ans("0");
for(char c: s1)
ans = ans * "10" + s2 * string(1, c);
return m[s1][s2] = ans;
}bool cmp(string s1, string s2){
if(s1.size() != s2.size())
return s1.size() > s2.size();
return s1 > s2;
}string operator-(string s1, string s2){
if(!cmp(s2, s1)){
reverse(s1.begin(), s1.end());
reverse(s2.begin(), s2.end());
s2.resize(s1.size(), '0');
s1.push_back('0');
for(size_t i = 0; i < s2.size(); ++i){
int k = s2[i] - '0';
s1[i] -= k;
if(s1[i] < '0'){
s1[i] += 10;
--s1[i + 1];
}
}while(s1.back() == '0')
s1.pop_back();
if(s1.empty())
return "0";
reverse(s1.begin(), s1.end());
return s1;
}else{
string s3 = s2 - s1;
auto it = s3.begin();
s3.insert(it, '-');
return s3;
}
}string power(string s, int k){
string ans = "1";
do{
if(k & 1)
ans = ans * s;
s = s * s;
}while(k >>= 1);
return ans;
}int main(){
scanf("%d", &n);
ans = power("2", n) - "1";
printf("%u", ans.size());
reverse(ans.begin(), ans.end());
ans.resize(500, '0');
reverse(ans.begin(), ans.end());
for(int i = 0; i < 500; ++i){
if(i % 50 == 0)
printf("\n");
putchar(ans[i]);
}return 0;
}
by allen2010 @ 2024-07-23 16:55:59
@cgxd 调不了一点,你的算法复杂度过高,不能暴力求位数,可以参考题解
by cgxd @ 2024-08-01 13:31:38
加法中加了
if(s1.size() > 500)
s1.resize(500);
将判断位数改为
printf("%d", int(log(2) / log(10) * n) + 1);
已过,此贴结