[已解决]高精度求助

额外减小

rt
OpenAI的垃圾ChatGPT请不要回答，谢谢。你的回复都是依托答辩。
好久没写高精度了。今天用c++重新写一遍，但是发现有很多漏洞,效率也很低，有人可以帮忙修正一下吗（在源代码的基础上），谢谢了。这是题目的网站。
注意，我要的不是AC代码模板，我想要在我原本代码的基础上的改进。（也可以说明我的问题在哪，我也会给你最佳）
代码如下。OpenAI的垃圾ChatGPT请不要回答，谢谢。你的回复都是依托答辩。

@zhangjinxuan @Mike_python小 @sfqxx @liuhongrun2022 @元豪

1. #include <iostream>
   
2. #include <typeinfo>
   
3. #include <string>
   
4. using namespace std;
   
5. 
   
6. inline int gjd_cmp(string a,string b)//a>b:return 1   a==b:return 0   a<b:return -1
   
7. {
   
8.         string num1(a),num2(b);
   
9.         while(num1[0]=='0' and num1.length()-1)
   
10.         {
    
11.                 num1.erase(0,1);
    
12.         }
    
13.         while(num2[0]=='0' and num2.length()-1)
    
14.         {
    
15.                 num2.erase(0,1);
    
16.         }
    
17.         if(num1.length()<num2.length())
    
18.         {
    
19.                 return -1;
    
20.         }
    
21.         if(num1.length()>num2.length())
    
22.         {
    
23.                 return 1;
    
24.         }
    
25.         for(int i=0,l=num1.length();i<l;i++)
    
26.         {
    
27.                 if(num1[i]>num2[i])
    
28.                 {
    
29.                         return 1;
    
30.                 }
    
31.                 if(num1[i]<num2[i])
    
32.                 {
    
33.                         return -1;
    
34.                 }
    
35.         }
    
36.         return 0;
    
37. }
    
38. 
    
39. inline string gjd_add(string a,string b)
    
40. {
    
41.         int sum=0;
    
42.         string num1(a),num2(b),ans;
    
43.         if(num1.length()>num2.length())
    
44.         {
    
45.                 num2.insert(0,num1.length()-num2.length(),'0');
    
46.         }
    
47.         else
    
48.         {
    
49.                 num1.insert(0,num2.length()-num1.length(),'0');
    
50.         }
    
51.         for(int i=num1.length()-1;i>=0;i--)
    
52.         {
    
53.                 sum+=num1[i]+num2[i]-2*'0';
    
54.                 ans.insert(0,1,sum%10+'0');
    
55.                 sum/=10;
    
56.         }
    
57.         if(sum)ans.insert(0,1,sum+'0');
    
58.         return ans;
    
59. }
    
60. 
    
61. inline string gjd_sub(string a,string b)
    
62. {
    
63.         int jw=0,op=0;
    
64.         string num1,num2,ans;//num1>num2
    
65.         if(gjd_cmp(a,b)>=0)num1=a,num2=b;
    
66.         else num1=b,num2=a,op=1;
    
67.         for(int i=num1.length()-1;i>=0;i--)
    
68.         {
    
69.                 if(num1[i]<num2[i]+jw)
    
70.                 {
    
71.                         ans.insert(0,1,num1[i]+10-num2[i]-jw+'0');
    
72.                         jw=1;
    
73.                 }
    
74.                 else
    
75.                 {
    
76.                         ans.insert(0,1,num1[i]-num2[i]-jw+'0');
    
77.                         jw=0;
    
78.                 }
    
79.         }
    
80.         while((ans[0]=='0')&&(ans.length()-1))
    
81.         {
    
82.                 ans.erase(0,1);
    
83.         }
    
84.         if(op)ans.insert(0,1,'-');
    
85.         return ans;
    
86. }
    
87. 
    
88. inline string gjd_sub1(string a,string b)
    
89. {
    
90.         int jw=0,op=0;
    
91.         string num1,num2,ans;//num1>num2
    
92.         if(gjd_cmp(a,b)>=0)num1=a,num2=b;
    
93.         else num1=b,num2=a,op=1;
    
94.         num2.insert(0,num1.length()-num2.length(),'0');
    
95.         for(int i=num1.length()-1;i>=0;i--)
    
96.         {
    
97.                 if(num1[i]<num2[i]+jw)
    
98.                 {
    
99.                         ans.insert(0,1,num1[i]+10-num2[i]-jw+'0');
    
100.                         jw=1;
     
101.                 }
     
102.                 else
     
103.                 {
     
104.                         ans.insert(0,1,num1[i]-num2[i]-jw+'0');
     
105.                         jw=0;
     
106.                 }
     
107.         }
     
108.         if(op)ans.insert(0,1,'-');
     
109.         return ans;
     
110. }
     
111. 
     
112. inline string gjd_mul(string a,string b)
     
113. {
     
114.         long long la=a.length(),lb=b.length();
     
115.         long long ia[la+50]={0},ib[lb+50]={0},ic[la+lb+100]={0};
     
116.        
     
117.         string ans;
     
118.         //num1.length()>num2.length()
     
119.         for(int i=la-1;i>-1;i--)
     
120.         {
     
121.                 ia[i]=a[la-i-1]-'0';
     
122.         }
     
123.         for(int i=lb-1;i>-1;i--)
     
124.         {
     
125.                 ib[i]=b[lb-i-1]-'0';
     
126.         }
     
127.         int sum=0,w=0;
     
128.         for(int i=0;i<la;i++)
     
129.         {
     
130.                 for(int j=0;j<lb;j++)
     
131.                 {
     
132.                         ic[i+j]+=ia[i]*ib[j];
     
133.                 }
     
134.         }
     
135.         for(int i=0;i<la+lb;i++)
     
136.         {
     
137.                 ic[i+1]+=ic[i]/10;
     
138.                 ans.insert(0,1,ic[i]%10+'0');
     
139.         }
     
140.         while((ans[0]=='0')&&(ans.length()-1))
     
141.         {
     
142.                 ans.erase(0,1);
     
143.         }
     
144.         return ans;
     
145. }
     
146. 
     
147. inline string gjd_div(string a,string b)
     
148. {
     
149.         string ans,tmp(a);
     
150.         if(gjd_cmp(a,b)==-1)return "0";
     
151.         if(gjd_cmp(a,b)==0)return "1";
     
152.         //a>b
     
153.         for(int i=b.length();i<=a.length();i++)
     
154.         {
     
155.                 if(gjd_cmp(tmp.substr(0,i),b)==-1)
     
156.                 {
     
157.                         ans.push_back('0');
     
158.                 }
     
159.                 else
     
160.                 {
     
161.                         for(int j=9;j>0;j--)
     
162.                         {
     
163.                                
     
164.                                 if(gjd_cmp(tmp.substr(0,i),gjd_mul(b,(string)""+(char)(j+'0')))!=-1)
     
165.                                 {
     
166.                                         tmp=gjd_sub1(tmp.substr(0,i),gjd_mul(b,(string)""+(char)(j+'0')))+tmp.substr(i,tmp.length());
     
167.                                         ans.push_back('0'+j);
     
168.                                         break;
     
169.                                 }
     
170.                         }
     
171.                 }
     
172.         }
     
173.         if(ans[0]=='0' and ans.length()-1) ans.erase(0,1);
     
174.         return ans;
     
175. }
     
176. 
     
177. inline string gjd_mod(string a,string b)
     
178. {
     
179.         return gjd_sub(a,gjd_mul(b,gjd_div(a,b)));
     
180. }
     
181. 
     
182. int main()
     
183. {
     
184.         string a,b;
     
185.         cin>>a>>b;
     
186.         string div=gjd_div(a,b);
     
187.         cout<<gjd_add(a,b)<<endl<<gjd_sub(a,b)<<endl<<gjd_mul(a,b)<<endl<<div<<endl<<gjd_sub(a,gjd_mul(b,div))<<endl;
     
188.        
     
189. }

复制代码

彩虹
https://www.luogu.com.cn/record/116845653

最佳答案

月排行榜 / 总排行榜

sfqxx

2023-7-22 21:01:45

zhangjinxuan 发表于 2023-7-22 10:26
把加减乘除都实现啦

我给你悄悄说一声，我只会加减，不会乘除

kkksc003是这样说的：  

可以将a[ i ]*b[ j ]的贡献全都在中间产物的第 i+j-1 位上，可以把所有贡献算出来，最后一口气处理所有进位问题,代码很长，展示部分

1. for (int i = 1;i <= lena;i++)
   
2.     for(int j =1;j<= lenb;j++)
   
3.         c[i+j-1] += a[i]*b[i]//计算贡献
   
4. 
   

复制代码

@额外减小 不知道是否有帮助

跳转到最佳答案楼层

额外减小

歌者文明清理员 发表于 2023-7-22 00:47
币

还不睡觉啊。

额外减小

歌者文明清理员 发表于 2023-7-22 00:51
是

那你快看看我的代码罢。

额外减小

歌者文明清理员 发表于 2023-7-22 00:54
我只看见了“回帖奖励”几个字

我不会C/C++

好吧

额外减小

注：好像主要是高精度减法函数的问题，大部分点都是line 2挂掉了

额外减小

sfqxx 发表于 2023-7-22 00:56
币

回答问题

额外减小

sfqxx 发表于 2023-7-22 01:05
这种题你不用 python 可惜了

我不想，python没法训练我的算法能力

额外减小

sfqxx 发表于 2023-7-22 01:46
。。。

...快睡觉吧

额外减小

zhangjinxuan 发表于 2023-7-22 10:27
不得不说你的代码的常数因子是真的大

是这样的，因为是我自己想的

额外减小

元豪 发表于 2023-7-22 07:35
第八句是什么意思？

string num1(a),num2(b);

应该是初始化为括号里面的字符串吧

额外减小

sfqxx 发表于 2023-7-22 21:01
kkksc003是这样说的：  

可以将a[ i ]*b[ j ]的贡献全都在中间产物的第 i+j-1 位上，可以把所有贡献算 ...

乘法我就是按这个算法做的。

额外减小

@@zhangjinxuan 你觉得我的加减部分效率如何？

1. inline int gjd_cmp(string a,string b)//a>b:return 1   a==b:return 0   a<b:return -1
   
2. {//比较大小，不解释
   
3.         string num1(a),num2(b);
   
4.         while(num1[0]=='0' and num1.length()-1)
   
5.         {
   
6.                 num1.erase(0,1);
   
7.         }
   
8.         while(num2[0]=='0' and num2.length()-1)
   
9.         {
   
10.                 num2.erase(0,1);
    
11.         }
    
12.         if(num1.length()<num2.length())
    
13.         {
    
14.                 return -1;
    
15.         }
    
16.         if(num1.length()>num2.length())
    
17.         {
    
18.                 return 1;
    
19.         }
    
20.         for(int i=0,l=num1.length();i<l;i++)
    
21.         {
    
22.                 if(num1[i]>num2[i])
    
23.                 {
    
24.                         return 1;
    
25.                 }
    
26.                 if(num1[i]<num2[i])
    
27.                 {
    
28.                         return -1;
    
29.                 }
    
30.         }
    
31.         return 0;
    
32. }
    
33. 
    
34. inline string gjd_add(string a,string b)
    
35. {
    
36.         int sum=0;
    
37.         string ans,num1(a),num2(b);
    
38.         if(num1.length()>num2.length())//补全位数
    
39.         {
    
40.                 num2.insert(0,num1.length()-num2.length(),'0');
    
41.         }
    
42.         else
    
43.         {
    
44.                 num1.insert(0,num2.length()-num1.length(),'0');
    
45.         }
    
46.         for(int i=num1.length()-1;i>=0;i--)
    
47.         {
    
48.                 sum+=num1[i]+num2[i]-2*'0';
    
49.                 ans.insert(0,1,sum%10+'0');//进位
    
50.                 sum/=10;
    
51.         }
    
52.         if(sum)ans.insert(0,1,sum+'0');
    
53.         return ans;
    
54. }
    
55. 
    
56. inline string gjd_sub(string a,string b)//有去除前导零
    
57. {
    
58.         int jw=0,op=0;
    
59.         string num1,num2,ans;//num1>num2
    
60.         if(gjd_cmp(a,b)>=0)num1=a,num2=b;
    
61.         else num1=b,num2=a,op=1;//num2 为减数，num1 为被减数
    
62.         num2.insert(0,num1.length()-num2.length(),'0');
    
63.         for(int i=num1.length()-1;i>=0;i--)
    
64.         {
    
65.                 if(num1[i]<num2[i]+jw)
    
66.                 {
    
67.                         ans.insert(0,1,num1[i]+10-num2[i]-jw+'0');
    
68.                         jw=1;
    
69.                 }
    
70.                 else
    
71.                 {
    
72.                         ans.insert(0,1,num1[i]-num2[i]-jw+'0');
    
73.                         jw=0;
    
74.                 }
    
75.         }
    
76.         for(int i=0;i<ans.length();i++)
    
77.         {
    
78.                 if(ans[i]!='0')
    
79.                 {
    
80.                         ans.erase(0,i);
    
81.                         break;
    
82.                 }
    
83.         }
    
84.         if(ans[0]=='0')ans="0";
    
85.         if(op)ans.insert(0,1,'-');
    
86.         return ans;
    
87. }

复制代码