ZackofZHOU @ 2023-10-17 21:29:26
本蒟蒻写了快速幂 , 带高精乘 , TLE了5个点 , 测试信息
代码:
#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int A[100010],B[100010],C[100010];
struct vli
{
vector <char> number;
bool minis_zero = false;
void Swap(vli b)
{
vector <char> n = b.number;
b.number = number;
number = n;
bool x = b.minis_zero;
b.minis_zero = minis_zero;
minis_zero = x;
}
void get_string(string s)
{
if(s[0] == '-')
{
minis_zero = true;
s.erase(s.begin() + 0);
}
number.clear();
for(int i = 0;i < s.size();i++)
number.push_back(s[i]);
}
void show()
{
for(int i = 0;i < number.size();i++)
cout << number[i];
cout << '\n';
}
};
vli operator-(vli a,int b)
{
vli ans;
int lena = a.number.size();
for(int i = lena - 1;i >= 0;i--)
A[lena - i] = a.number[i] - '0';
A[1] -= b;
for(int i = 1;i <= lena;i++)
if(A[i] < 0)
A[i] += 10,A[i + 1]--;
for(;A[lena] == 0;)
lena--;
for(int i = lena;i >= 1;i--)
ans.number.push_back(A[i] + '0');
for(int i = 0;i < 1010;i++)
A[i] = 0,C[i] = 0;
return ans;
}
vli operator*(vli a,vli b)
{
vli ans;
int lena = a.number.size(),lenb = b.number.size(),len = lena + lenb;
for(int i = 0;i < lena;i++)
A[lena - i] = a.number[i] - '0';
for(int i = 0;i < lenb;i++)
B[lenb - i] = b.number[i] - '0';
for(int i = 1;i <= lena;i++)
for(int j = 1;j <= lenb;j++)
C[i + j - 1] += A[i] * B[j];
for(int i = 1;i <= len;i++)
{
C[i + 1] += (C[i] / 10);
C[i] %= 10;
}
for(;C[len] == 0;)
len--;
for(int i = len;i >= 1;i--)
ans.number.push_back(C[i] + '0');
for(int i = 0;i < 10010;i++)
A[i] = B[i] = C[i] = 0;
return ans;
}
int main()
{
vli ans,two,s;
int p,c = 0;
ans.get_string("1");
two.get_string("2");
s = two;
cin >> p;
while(p > 0)
{
if(p & 1)
ans = ans * s;
s = s * s;
p >>= 1;
}
ans = ans - 1;
cout << ans.number.size() << '\n';
if(ans.number.size() >= 500)
for(int i = ans.number.size() - 500;i < ans.number.size();i++)
{
c++;
cout << ans.number[i];
if(c % 50 == 0)
cout << '\n';
}
else
{
for(int i = 1;i <= 500 - ans.number.size();i++)
{
c++;
cout << 0;
if(c % 50 == 0)
cout << '\n';
}
for(int i = 0;i < ans.number.size();i++)
{
c++;
cout << ans.number[i];
if(c % 50 == 0)
cout << '\n';
}
}
return 0;
}
请求各位
by Turtle_Coffee @ 2023-10-17 21:46:31
qp(doge)