共计 2927 个字符，预计需要花费 8 分钟才能阅读完成。
从前的大数模拟都是自己用字符串来敲的, 突然看到同学的代码后释放了很多思维, 不仅敲得快还不容易错, 于是找个晚上敲下大数的一些模拟, 留下板子记录一下.
对于负数加减模拟运算我们可以分情况讨论并编写另一个函数, 即:
若两数均正 ans = add(a,b)
若两数均负 ans = ‘-‘ + add(a,b)
若一正一负 ans = sub(a,b) or ans = sub(b,a)
可拟函数
string add_op(string a,string b)
{
string ans;
if(a[0] == ‘-‘ && b[0] == ‘-‘){
a.erase(a.begin());
b.erase(b.begin());
ans = ‘-‘ + big_add(a,b);
}
else if(a[0] == ‘-‘){
a.erase(a.begin());
ans = big_sub(b,a);
}
else if(b[0] == ‘-‘){
b.erase(b.begin());
ans = big_sub(a,b);
}
else{
ans = big_add(a,b);
}
return ans;
}
大数加法
// 不支持负数
const int MAXN = 1e5 + 10;
int t[MAXN];
string big_add(string a,string b){
int len1 = a.size();
int len2 = b.size();
reverse(a.begin(),a.end()); // 调换顺序方便处理
reverse(b.begin(),b.end());
if(len1 < len2){
swap(a,b); // 令 a 是数位较长的数
swap(len1,len2);
}
for(int i = 0;i < len2;++i){// t 数组存在第 i 位上两数相加的结果, 暂时不进位
t[i] = a[i] -‘0’ + b[i] – ‘0’;
}
for(int i = len2;i < len1;++i){
t[i] = a[i] – ‘0’;
}
int flag = 0; //flag 标志是否需要进位
for(int i = 0;i < len1;++i){
if(flag) {
t[i]++;
flag = 0;
}
if(t[i] >= 10){
t[i]-=10;
flag = 1;
}
}
if(flag) t[len1] = 1; // 处理最高位是否需要进位, 若不需要令最高位为 0
else t[len1] = 0;
string ans;
flag = 0;
for(int i = len1;i >= 0 ;–i){// 去除前导 0
if(flag == 0 && t[i] == 0) continue;
flag = 1;
ans.push_back(t[i] + ‘0’);
}
return ans;
}
大数减法
const int MAXN = 1e8 + 10;
int t[MAXN];
string big_sub(string a,string b)
{
string ans;
int pos = 0; // 标记结果是否为负数
if(a.size() < b.size() ||( a < b && a.size() == b.size())) {
swap(a,b);
pos = 1;
}
int len1 = a.size();
int len2 = b.size();
reverse(a.begin(),a.end()); // 调换顺序便于处理
reverse(b.begin(),b.end());
for(int i = 0;i < len2 ;++i){// t 数组保存第 i 位上两数之差
t[i] = a[i] – b[i];
}
for(int i = len2;i < len1;++i){
t[i] = a[i] – ‘0’; // 若 a 位数较长, 则长度超过 b 的位结果为 a[i] – 0
}
int flag = 0;
for(int i = 0;i < len1;++i){// 借位
if(flag){
flag = 0;
t[i]–;
}
if(t[i] < 0){
t[i]+=10;
flag = 1;
}
}
flag = 0;
for(int i = len1-1;i >= 0;–i){// 去除前导 0
if(!flag && t[i] == 0) continue;
flag = 1;
ans.push_back(t[i] + ‘0’);
}
if(ans.empty()) ans.push_back(‘0’); // 若结果为 0, 答案 ans = 0
if(pos && ans[0] != ‘0’) ans = ‘-‘ + ans;
return ans;
}
大数乘法
int t[10000000];
string mul(string a,string b)
{
reverse(a.begin(),a.end()); // 交换顺序，方便计算
reverse(b.begin(),b.end());
int len1=a.size();
int len2=b.size();
for(int i = 0;i < len1;++i)
for(int j = 0;j < len2;++j)
t[i+j]=(a[i]-‘0’)*(b[j]-‘0′)+t[i+j]; // 先整体乘起来，不进位
int over=0;
for(int i = 0;i < len1+len2;++i) // 进位
{
t[i]+=over;
over=0;
if(t[i]>=10)
{
over=t[i]/10;
t[i]%=10;
}
}
string c;
for(int i = 0;i < len1+len2;++i)
{
c+=(t[i]+’0’);
}
return c;
}
大数求模
// 大数求模就很简单了, 根据同余定理来按位求模就好了
long long big_mod(string a,long long mod)
{
int len=a.size();
long long ans=0;
for(int i=0;i<len;++i)
ans=(ans*10%mod+a[i]-‘0’)%mod;
return ans;
}
大数求幂
// 还不太会, 先留个板子 (留坑)
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
typedef long long ll;
ll phi(ll n)
{
int ans = n, temp = n;
for (int i = 2; i*i <= temp; i++)
{
if (temp%i == 0)
{
ans -= ans / i;
while (temp%i == 0) temp /= i;
}
}
if (temp > 1) ans -= ans / temp;
return ans;
}
ll mod_pow(ll x, ll n, ll mod) // 快速幂
{
ll ans = 1;
while (n)
{
if (n % 2 == 1)
ans = ans * x%mod;
x = x * x%mod;
n /= 2;
}
return ans;
}
char a[1000010],b[1000010];
int main()
{
scanf(“%s%s”, a, b);
ll phic = phi(mod);
int i, len = strlen(a);
ll res = 0, ans;
for (i = 0; i < len; i++)
{
res = res * 10 + a[i] – ‘0’;
if (res > phic)
break;
}
if (i == len)
{
ans = mod_pow(2, res, mod) % mod;
}
else
{
res = 0;
for (int i = 0; i < len; i++)
{
res = res * 10 + a[i] – ‘0’;
res %= phic;
}
ans = mod_pow(2, res + phic, mod) % mod;
}
cout << ans << endl;
return 0;
}
