[已解决]高精度求助

额外减小

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

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

#include <iostream>
#include <typeinfo>
#include <string>
using namespace std;

inline int gjd_cmp(string a,string b)//a>b:return 1   a==b:return 0   a<b:return -1
{
        string num1(a),num2(b);
        while(num1[0]=='0' and num1.length()-1)
        {
                num1.erase(0,1);
        }
        while(num2[0]=='0' and num2.length()-1)
        {
                num2.erase(0,1);
        }
        if(num1.length()<num2.length())
        {
                return -1;
        }
        if(num1.length()>num2.length())
        {
                return 1;
        }
        for(int i=0,l=num1.length();i<l;i++)
        {
                if(num1[i]>num2[i])
                {
                        return 1;
                }
                if(num1[i]<num2[i])
                {
                        return -1;
                }
        }
        return 0;
}

inline string gjd_add(string a,string b)
{
        int sum=0;
        string num1(a),num2(b),ans;
        if(num1.length()>num2.length())
        {
                num2.insert(0,num1.length()-num2.length(),'0');
        }
        else
        {
                num1.insert(0,num2.length()-num1.length(),'0');
        }
        for(int i=num1.length()-1;i>=0;i--)
        {
                sum+=num1[i]+num2[i]-2*'0';
                ans.insert(0,1,sum%10+'0');
                sum/=10;
        }
        if(sum)ans.insert(0,1,sum+'0');
        return ans;
}

inline string gjd_sub(string a,string b)
{
        int jw=0,op=0;
        string num1,num2,ans;//num1>num2
        if(gjd_cmp(a,b)>=0)num1=a,num2=b;
        else num1=b,num2=a,op=1;
        for(int i=num1.length()-1;i>=0;i--)
        {
                if(num1[i]<num2[i]+jw)
                {
                        ans.insert(0,1,num1[i]+10-num2[i]-jw+'0');
                        jw=1;
                }
                else
                {
                        ans.insert(0,1,num1[i]-num2[i]-jw+'0');
                        jw=0;
                }
        }
        while((ans[0]=='0')&&(ans.length()-1))
        {
                ans.erase(0,1);
        }
        if(op)ans.insert(0,1,'-');
        return ans;
}

inline string gjd_sub1(string a,string b)
{
        int jw=0,op=0;
        string num1,num2,ans;//num1>num2
        if(gjd_cmp(a,b)>=0)num1=a,num2=b;
        else num1=b,num2=a,op=1;
        num2.insert(0,num1.length()-num2.length(),'0');
        for(int i=num1.length()-1;i>=0;i--)
        {
                if(num1[i]<num2[i]+jw)
                {
                        ans.insert(0,1,num1[i]+10-num2[i]-jw+'0');
                        jw=1;
                }
                else
                {
                        ans.insert(0,1,num1[i]-num2[i]-jw+'0');
                        jw=0;
                }
        }
        if(op)ans.insert(0,1,'-');
        return ans;
}

inline string gjd_mul(string a,string b)
{
        long long la=a.length(),lb=b.length();
        long long ia[la+50]={0},ib[lb+50]={0},ic[la+lb+100]={0};
        
        string ans;
        //num1.length()>num2.length()
        for(int i=la-1;i>-1;i--)
        {
                ia[i]=a[la-i-1]-'0';
        }
        for(int i=lb-1;i>-1;i--)
        {
                ib[i]=b[lb-i-1]-'0';
        }
        int sum=0,w=0;
        for(int i=0;i<la;i++)
        {
                for(int j=0;j<lb;j++)
                {
                        ic[i+j]+=ia[i]*ib[j];
                }
        }
        for(int i=0;i<la+lb;i++)
        {
                ic[i+1]+=ic[i]/10;
                ans.insert(0,1,ic[i]%10+'0');
        }
        while((ans[0]=='0')&&(ans.length()-1))
        {
                ans.erase(0,1);
        }
        return ans;
}

inline string gjd_div(string a,string b)
{
        string ans,tmp(a);
        if(gjd_cmp(a,b)==-1)return "0";
        if(gjd_cmp(a,b)==0)return "1";
        //a>b
        for(int i=b.length();i<=a.length();i++)
        {
                if(gjd_cmp(tmp.substr(0,i),b)==-1)
                {
                        ans.push_back('0');
                }
                else
                {
                        for(int j=9;j>0;j--)
                        {
                                
                                if(gjd_cmp(tmp.substr(0,i),gjd_mul(b,(string)""+(char)(j+'0')))!=-1)
                                {
                                        tmp=gjd_sub1(tmp.substr(0,i),gjd_mul(b,(string)""+(char)(j+'0')))+tmp.substr(i,tmp.length());
                                        ans.push_back('0'+j);
                                        break;
                                }
                        }
                }
        }
        if(ans[0]=='0' and ans.length()-1) ans.erase(0,1);
        return ans;
}

inline string gjd_mod(string a,string b)
{
        return gjd_sub(a,gjd_mul(b,gjd_div(a,b)));
}

int main()
{
        string a,b;
        cin>>a>>b;
        string div=gjd_div(a,b);
        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;
        
}

彩虹
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 位上，可以把所有贡献算出来，最后一口气处理所有进位问题,代码很长，展示部分

for (int i = 1;i <= lena;i++)

    for(int j =1;j<= lenb;j++)

        c[i+j-1] += a[zxsq-anti-bbcode-i]*b[zxsq-anti-bbcode-i]//计算贡献

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

跳转到最佳答案楼层

额外减小

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

Mike_python小

你好！我可以帮助你改进你的高精度计算代码。我已经仔细阅读了你的代码，并发现了几个问题和改进的地方。下面是我对每个函数的建议：

1. gjd_cmp 函数：
   - 在比较字符串长度之前，确保 num1 和 num2 的长度大于 0。
   - 在最后用以比较大小的循环中，应该添加一个条件来处理当字符串长度相等时的情况。

2. gjd_add 函数：
   - 使用引用传递来避免不必要的拷贝操作。
   - 在函数内部声明变量时，使用更具描述性的名称。

3. gjd_sub 函数：
   - 使用引用传递来避免不必要的拷贝操作。
   - 在函数内部声明变量时，使用更具描述性的名称。
   - 可以简化代码逻辑，减少重复的判断语句。

4. gjd_sub1 函数：
   - 使用引用传递来避免不必要的拷贝操作。
   - 在函数内部声明变量时，使用更具描述性的名称。
   - 可以简化代码逻辑，减少重复的判断语句。

5. gjd_mul 函数：
   - 使用引用传递来避免不必要的拷贝操作。
   - 在函数内部声明变量时，使用更具描述性的名称。

6. gjd_div 函数：
   - 使用引用传递来避免不必要的拷贝操作。
   - 在函数内部声明变量时，使用更具描述性的名称。
   - 可以使用 string 类型的构造函数简化代码。

7. gjd_mod 函数：
   - 使用引用传递来避免不必要的拷贝操作。
   - 在函数内部声明变量时，使用更具描述性的名称。

除了上述建议，你还可以考虑以下改进：

- 考虑使用 std::vector 或自定义的类来表示大整数，这样可以更方便地进行运算和处理。
- 优化乘法运算，可以使用 Karatsuba 算法或其他快速的大整数乘法算法。

希望以上建议对你有帮助！如果你有任何疑问，请随时提问。

球一个最佳答案谢谢啦！这对我非常重要！

isdkz

首先，我非常高兴您在这里寻求帮助。我看到了你的代码，你已经非常接近解决问题了，但有几个地方可能需要改进，我会为你详细说明。

1. 函数gjd_cmp:
   在此函数中，你一直在删除数字前的0，这种方式相对效率较低。因为string的erase操作时间复杂度为O(n)。所以在数字长度非常长的情况下，这会浪费很多时间。我们可以直接找到第一个非零的位置，然后从那里开始比较，这样可以提高效率。

2. 函数gjd_sub和gjd_sub1:
   这两个函数几乎相同，只是在处理输入长度时有所不同。这可能会导致代码冗余。我们可以合并这两个函数，将处理长度的部分做成条件判断。

3. 函数gjd_mul:
   这个函数的效率可以进一步提高。在你的实现中，你遍历每一位，然后一位一位地进行乘法和加法，这实际上是一个O(n^2)的算法。有一种更好的方法叫做Karatsuba算法，该算法可以将复杂度降低到O(n^1.585)，这将大大提高效率。

4. 函数gjd_div:
   这个函数中，每一位都调用了乘法和比较函数，这可能会导致效率低下。实际上，你可以使用二分法找到每一位的值，这将大大提高效率。

以上就是我对你代码的一些改进建议。请注意，编写高精度计算的代码时，需要特别关注性能和效率。希望我的建议能够对你有所帮助，如果你还有其他问题，欢迎随时提问。

歌者文明清理员

币

Threebody1

币

Threebody1

币

额外减小

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

还不睡觉啊。

歌者文明清理员

额外减小 发表于 2023-7-22 00:50
还不睡觉啊。

是

额外减小

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

那你快看看我的代码罢。

歌者文明清理员

额外减小 发表于 2023-7-22 00:51
那你快看看我的代码罢。

我只看见了“回帖奖励”几个字

我不会C/C++

额外减小

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

我不会C/C++

好吧

sfqxx

币

额外减小

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

回答问题

sfqxx

额外减小 发表于 2023-7-22 00:57
回答问题

中了再说

isdkz

币

sfqxx

这种题你不用 python 可惜了

sfqxx

中奖绝缘体

额外减小

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

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

sfqxx

额外减小 发表于 2023-7-22 01:12
我不想，python没法训练我的算法能力

。。。