高精度除以高精度pythonJosephtony的博客-

让我们一起听着马克西姆的Still Water走进IT天堂…
沉默的雨，无声胜有声;逗人的雨，真叫人喜悦。可以不必穿雨衣，在户外踯躅漫步，雨似蜜似酒，滋润着心灵。雨，好像是千万支魔指，好像是千万条琴弦，弹出了千变万化的声音。
废话过多，让我们走进正题吧…

题目描述
给出正整数N和M，请你计算N div M（N/M的下取整）。

输入格式
两行，两个正整数，N和M。

输出格式
一行，一个整数，表示N div M。

• 对于60%的数据：N，M ≤ 750!，答案≤ 7!。

• 对于100%的数据：N，M ≤ 6250!，答案≤ 13!。

看着这些莫名其妙的感叹号，我不禁拿出了计算器，6250×6249×6248×6247×…6244×6243=…
很明显，数字太大了！
（为什么c++不像python一样自带高精度！！！！！！！）

说多话也没用，上代码！

时间复杂度过高，不宜使用

#include<iostream> #include<cstdio> #include<cstring> using namespace std; int a[100005]={0},b[100005]={0},ans[100005]={0},la,lb,lens,i,j,k;//a：被除数；b：除数；ans：商;la：被除数长度；lb：除数长度；lans：商长度i，j，k：循环用 char s1[100005]={0},s2[100005]={0}; int main() {  cin>>s1>>s2;//读入  la=strlen(s1);  lb=strlen(s2); for(i=1;i<=la;i++) {   a[i]=s1[i-1]-'0'; } for(i=1;i<=lb;i++) {   b[i]=s2[i-1]-'0';//将字符串转换成数组 } if(la<lb)//如果被除数比除数的长度短，直接输出0 {   cout<<"0"; return 0; } if(la==lb)//如果长度一样，若被除数较小，同样输出0 { for(i=1;i<=la;i++) { if(a[i]<b[i]) {     cout<<0; return 0; } else { if(a[i]>b[i]) { break; } } } }  lens=la-lb+1;//把除法转换成减法，不停地减，每减一次，对应位置的答案加一 for(i=1;i<=lens;i++) { while(1) { for(j=i,k=1;j<=lb+i-1,k<=lb;j++,k++) { if(a[j]>b[k])//如果被除数的某位置先比除数大了，则可以做减法，跳出循环 {      j=lb+1; break; } else { if(a[j]<b[k])//如果被除数的某位置先比除数小了，则不可做减法，跳出循环 { break;//若两数相同，则继续循环判断 } } } if(j>lb)//如果可以做减法 { for(j=lb+i-1,k=lb;j>=i,k>=1;j--,k--) { if(a[j]-b[k]>=0) {       a[j]-=b[k];//减法实现 } else {       a[j]+=10,a[j-1]--,a[j]-=b[k];//如果一个位置上的数小于零，则退位 } }     ans[i]++; } else//如果不能做减法 {     a[i+1]+=a[i]*10;//将最前一位的所有数全部退到下一位置的数上     a[i]=0;//归零 break;//跳出减法循环 } } } for(i=1;i<=lens;i++) { if(i==1&&ans[i]==0);//删去前导0 else {    cout<<ans[i]; } } return 0; } 

时间复杂度过高，不建议使用

稻花香里说丰年，听取WA声一片