TLE 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
vector<int> lmul(vector<int> &a,vector<int> &b){
vector<int> c;
int max_size=a.size()+b.size();
c.assign(max_size,0);
for(int i=0;i<b.size();i++){
for(int j=0;j<a.size();j++)c[i+j]+=a[j]*b[i];
}
for(int i=0;i<c.size()-1;i++){
if(c[i]>9){
c[i+1]+=c[i]/10;
c[i]%=10;
}
}
while(c.size()>1 && c.back()==0)c.pop_back();
return c;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int p;
cin>>p;
vector<int>res(1,1),a(1,2);
while(p){
if(p&1)res=lmul(res,a);
a= lmul(a,a);
p>>=1;
}
res[0]--;
for(int i=0;i<=res.size()-2;i++){
if(res[i]<0){
res[i]+=10;
res[i+1]--;
}
}
while(res.size()>1 && res.back()==0)res.pop_back();
cout<<res.size()<<'\n';
if(res.size()<500) {
while (res.size() < 500)res.push_back(0);
int pos = res.size() - 1;
for (int t = 1; t <= 10; t++) {
for (int i = 1; i <= 50; i++) {
cout << res[pos--];
}
cout << '\n';
}
}
else {
for(int i=499;i>=450;i--)cout<<res[i];cout<<'\n';
for(int i=449;i>=400;i--)cout<<res[i];cout<<'\n';
for(int i=399;i>=350;i--)cout<<res[i];cout<<'\n';
for(int i=349;i>=300;i--)cout<<res[i];cout<<'\n';
for(int i=299;i>=250;i--)cout<<res[i];cout<<'\n';
for(int i=249;i>=200;i--)cout<<res[i];cout<<'\n';
for(int i=199;i>=150;i--)cout<<res[i];cout<<'\n';
for(int i=149;i>=100;i--)cout<<res[i];cout<<'\n';
for(int i=99;i>=50;i--)cout<<res[i];cout<<'\n';
for(int i=49;i>=0;i--)cout<<res[i];cout<<'\n';
}
return 0;
}
TLE原因分析:
双高精乘法时间复杂度O(n*n)会超时
而求位数可以用log10()结合换底公式求(注意2^p与2^p-1一定位数相同,因为最低位不为0)
每次计算只要过500位就结束,即只保证最低500位是对的就好,因为要去除前导0,为保险用510
ac代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
vector<int> lmul(vector<int> &a,vector<int> &b){
vector<int> c;
int max_size=a.size()+b.size();
c.assign(max_size,0);
for(int i=0;i<b.size();i++){
for(int j=0;j<a.size();j++){
if(i+j>=510)continue;
c[i+j]+=a[j]*b[i];
}
}
for(int i=0;i<c.size()-1;i++){
if(c[i]>9){
c[i+1]+=c[i]/10;
c[i]%=10;
}
if(i>=510)break;
}
while(c.size()>1 && c.back()==0)c.pop_back();
return c;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int p;
cin>>p;
cout<<(int)(log10(2)*p)+1<<'\n';
vector<int>res(1,1),a(1,2);
while(p){
if(p&1)res=lmul(res,a);
a= lmul(a,a);
p>>=1;
}
res[0]--;
for(int i=0;i<=res.size()-2;i++){
if(res[i]<0){
res[i]+=10;
res[i+1]--;
}
}
while(res.size()>1 && res.back()==0)res.pop_back();
if(res.size()<500) {
while (res.size() < 500)res.push_back(0);
int pos = res.size() - 1;
for (int t = 1; t <= 10; t++) {
for (int i = 1; i <= 50; i++) {
cout << res[pos--];
}
cout << '\n';
}
}
else {
for(int i=499;i>=450;i--)cout<<res[i];cout<<'\n';
for(int i=449;i>=400;i--)cout<<res[i];cout<<'\n';
for(int i=399;i>=350;i--)cout<<res[i];cout<<'\n';
for(int i=349;i>=300;i--)cout<<res[i];cout<<'\n';
for(int i=299;i>=250;i--)cout<<res[i];cout<<'\n';
for(int i=249;i>=200;i--)cout<<res[i];cout<<'\n';
for(int i=199;i>=150;i--)cout<<res[i];cout<<'\n';
for(int i=149;i>=100;i--)cout<<res[i];cout<<'\n';
for(int i=99;i>=50;i--)cout<<res[i];cout<<'\n';
for(int i=49;i>=0;i--)cout<<res[i];cout<<'\n';
}
return 0;
}