高精度乘法（Trachtenberg速算法）

一.介绍： Trachtenberg速算法：（转载） 二.代码实现： #include #include #include #include #i
2023-12-07 技术

一.介绍：

Trachtenberg速算法：（转载）

二.代码实现：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define eps 1e-4
#define PI acos(-1.0)
#define ll long long int
using namespace std;struct node
{int pos;char num;
};const int M = 1010;
struct node a[M], b[M];
int len = 0;
int len1 = 0;
int len2 = 0;
int ans[M * M];void Print()
{int i = len;while(!ans[i])i--;for(; i >= 0; --i)printf("%d", ans[i]);printf("\n");
}void Trachtenberg()
{while(b[0].pos != len1 + 1){for(int i = 0; i < len2; ++i){if(b[i].pos == 0)ans[len] += ((b[i].num - '0') * (a[len1 - 1].num - '0')) % 10;else if(b[i].pos == len1)ans[len] += ((b[i].num - '0') * (a[0].num - '0')) / 10;else if(b[i].pos > 0 && b[i].pos < len1)ans[len] += ((b[i].num - '0') * (a[len1 - b[i].pos - 1].num - '0')) % 10 + ((b[i].num - '0') * (a[len1 - b[i].pos].num - '0')) / 10;b[i].pos++;}ans[len + 1] += ans[len] / 10;ans[len] %= 10;len++;}Print();
}void Scan(string s1, string s2)
{len1 = s1.size();len2 = s2.size();for(int i = 0; i < len1; ++i)a[i].num = s1[i];for(int i = 0; i < len2; ++i)b[i].num = s2[i];for(int i = len2 - 1; i >= 0; --i){if(i == len2 - 1)b[i].pos = 0;elseb[i].pos = b[i + 1].pos - 1;}
}int main()
{string s1, s2;cin >> s1 >> s2;Scan(s1, s2);if(a[0].num == '0' && len1 == 1 || b[0].num == '0' && len2 == 1)printf("0\n");elseTrachtenberg();return 0;
}

 

版权声明

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！

推荐阅读