高精度运算
今天模拟，很巧的是我前两天刚看过这个qwq
高精度加法 高精度减法 高精度乘 高精度阶乘 别看了，写的没有我好
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。某人为数不多的写了blog的题解
我麻了，这个人怎么会是我师父
高精度运算需要使用python
因为在十进制，int最多十位，long long最多十九位，
要算比这个还大的数，就要把它拆成一位一位，模拟列竖式计算，也就是高精度
输入和输出
char s1[maxn],s2[maxn]; int d1[maxn],d2[maxn];
首先把两个数以字符串的形式读入，然后把它们转化成int；
for(int i = 0; i <= len1; i++) d1[len1-i] = s1[i]-'0';
（这么写的好处是，数组的下标由原来的0~len-1变成了1~len）
计算；
最后倒序输出，忽略前导0。只剩一位的时候0要保留。
while(k>1) { if(ans[k])break; k--; } for(int i = k; i; i--) printf("%d",ans[i]);
高精度加法
计算时，注意判断是否进位。加法最多只能进一位，所以$ans[i+1]+1,ans[i]-10$即可。
#include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<string>
#define MogeKo qwq
using namespace std; const int maxn = 1e6+10; char s1[maxn],s2[maxn]; int len1,len2,k; int d1[maxn],d2[maxn],ans[maxn]; int main() { scanf("%s",s1); scanf("%s",s2); len1 = strlen(s1),len2 = strlen(s2); for(int i = 0; i <= len1; i++) d1[len1-i] = s1[i]-'0'; for(int i = 0; i <= len2; i++) d2[len2-i] = s2[i]-'0'; while(++k <= max(len1,len2)) { ans[k] += d1[k]+d2[k]; if(ans[k]>=10) { ans[k+1]++; ans[k] -= 10; } } while(k>1) { if(ans[k])break; k--; } for(int i = k; i; i--)printf("%d",ans[i]); return 0; }
+
高精度减法
同理，只能借一位，$ans[i+1]-1,ans[i]+10$。
注意：需要先判断答案的正负，先比较两个数字的位数，再一位一位比较，
如果前面的较小，则交换两个数组并输出负号。相等则按正数算。
#include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<string>
#define MogeKo qwq
using namespace std; const int maxn = 1e6+10; char s1[maxn],s2[maxn]; int len1,len2,k; int d1[maxn],d2[maxn],ans[maxn]; bool check() { if(len1 > len2)return true; if(len1 < len2)return false; for(int i = len1; i; i--) { if(d1[i]>d2[i])return true; if(d1[i]<d2[i])return false; } return true; } int main() { scanf("%s",s1); scanf("%s",s2); len1 = strlen(s1),len2 = strlen(s2); for(int i = 0; i <= len1; i++) d1[len1-i] = s1[i]-'0'; for(int i = 0; i <= len2; i++) d2[len2-i] = s2[i]-'0'; if(!check()) { printf("-"); swap(d1,d2); swap(len1,len2); } while(++k <= max(len1,len2)) { ans[k] += d1[k]-d2[k]; if(ans[k]<0) { ans[k+1]--; ans[k] += 10; } } while(k>1) { if(ans[k])break; k--; } for(int i = k; i; i--)printf("%d",ans[i]); return 0; }
-
高精度乘法
设第一个数枚举到$d[i]$，第二个数枚举到$d[j]$，则当前算出来的的数字为$ans[i+j-1]$。
可能进不止一位，则$ans[i+1]+ans[i]/10,ans[i] mod 10$。
注意数据范围，数组的大小应为$n^2$
#include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<string>
#define MogeKo qwq
using namespace std; const int maxn = 1e6+10; char s1[maxn],s2[maxn]; int len1,len2,k; int d1[maxn],d2[maxn],ans[maxn]; int main() { scanf("%s",s1); scanf("%s",s2); len1 = strlen(s1),len2 = strlen(s2); for(int i = 0; i <= len1; i++) d1[len1-i] = s1[i]-'0'; for(int i = 0; i <= len2; i++) d2[len2-i] = s2[i]-'0'; for(int i = 1;i <= len1;i++) for(int j = 1;j <= len2;j++){ int t = i+j-1; ans[t] += d1[i] * d2[j]; if(ans[t]>=10){ ans[t+1] += ans[t]/10; ans[t] %= 10; } } k = len1+len2+1; while(k>1) { if(ans[k])break; k--; } for(int i = k; i; i--)printf("%d",ans[i]); return 0; }
*
高精度阶乘
当要求一个较大数的阶乘时，需要应用到高精度乘法。
$n! = n*(n-1)!$，
用当前枚举到的数$n$与已经得到的数$(n-1)!$的各个数位相乘，即低精度*高精度。
注意这里不能直接$ans[i+1]+ans[i]/10$。因为$ans[i+1]$下一步还要与$n$相乘，乘法的优先级高于加法的优先级。
可以用一个$tem$记录进位，$ans[i+1]$完成乘法操作后再加上$tem$。
注意，枚举答案的每一位时，每次记录答案现在的位数比较麻烦，可以每次枚举到可能的最大值。
估算N的阶乘位数可以用斯特林公式……emm还是算了吧。
（100！约有158位，1000！约有2568位，10000！约有35660位）
#include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<string>
#define MogeKo qwq
using namespace std; const int maxn = 1e6+10; int n,k,t; int ans[maxn]; int main() { scanf("%d",&n); ans[1] = 1; k = 10000; for(int i = 1;i <= n;i++) for(int j = 1;j <= k;j++){ ans[j] *= i; ans[j] += t; t = 0; if(ans[j]>=10){ t = ans[j]/10; ans[j] %= 10; } } while(k>1) { if(ans[k])break; k--; } for(int i = k; i; i--)printf("%d",ans[i]); return 0; }
!
（然而并不会写除法）
