自我感觉良好的大数模拟

从前的大数模拟都是自己用字符串来敲的,突然看到同学的代码后释放了很多思维,不仅敲得快还不容易错,于是找个晚上敲下大数的一些模拟,留下板子记录一下.对于负数加减模拟运算我们可以分情况讨论并编写另一个函数,即:若两数均正 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=(ans10%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;}