3123. 高精度乘法II
2022/7/23 6:24:12
本文主要是介绍3123. 高精度乘法II,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接
3123. 高精度乘法II
给定两个正整数 \(A\) 和 \(B\),请你计算 \(A \times B\) 的值。
输入格式
共两行,第一行包含整数 \(A\),第二行包含整数 \(B\)。
输出格式
共一行,包含 \(A \times B\) 的值。
数据范围
\(1 \le A与B的长度 \le 10^5\)。
输入样例:
2 3
输出样例:
6
解题思路
fft
设 \(A\) 由高位到低位的值分别为 \(a_0,a_1,\dots,a_{n-1}\),构造一个 \(n-1\) 次多项式 \(f(x)=a_0+a_1x+a_2x^2+\dots +a_{n-1}x^{n-1}\),同理由 \(B\) 构造的多项式 \(g(x)=b_0+b_1x+b_2x^2+\dots +b_{m-1}x^{m-1}\),而 \(A=f(10),B=g(10)\),要求 \(A\times B=f(10)\times g(10)\),而 \(fft\) 可求得 \(h(x)=f(x)\times g(x)\),最后即求 \(h(10)\)。注意求解的 \(h(x)\) 的系数并不是最后的答案,其系数也可能不是一位数
- 时间复杂度:\(O(nlogn)\)
代码
// Problem: 高精度乘法II // Contest: AcWing // URL: https://www.acwing.com/problem/content/3126/ // Memory Limit: 64 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) // %%%Skyqwq #include <bits/stdc++.h> //#define int long long #define help {cin.tie(NULL); cout.tie(NULL);} #define pb push_back #define fi first #define se second #define mkp make_pair using namespace std; typedef long long LL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; } template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; } template <typename T> void inline read(T &x) { int f = 1; x = 0; char s = getchar(); while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); } while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar(); x *= f; } const int N=3e5+5; const double pi=acos(-1); int n,m,bit,tot,rev[N],res[N]; char A[N],B[N]; struct cp { double x,y; cp operator+(const cp &o)const { return {x+o.x,y+o.y}; } cp operator-(const cp &o)const { return {x-o.x,y-o.y}; } cp operator*(const cp &o)const { return {x*o.x-y*o.y,x*o.y+y*o.x}; } }a[N],b[N]; void fft(cp a[],int inv) { for(int i=0;i<tot;i++) if(i<rev[i])swap(a[i],a[rev[i]]); for(int mid=1;mid<tot;mid<<=1) { cp w1={cos(pi/mid),inv*sin(pi/mid)}; for(int i=0;i<tot;i+=mid<<1) { cp wk={1,0}; for(int j=0;j<mid;j++,wk=wk*w1) { cp x=a[i+j],y=a[i+j+mid]; a[i+j]=x+wk*y,a[i+j+mid]=x-wk*y; } } } } int main() { help; cin>>A>>B; n=strlen(A),m=strlen(B); n--,m--; for(int i=0;i<=n;i++)a[i].x=A[n-i]-'0'; for(int i=0;i<=m;i++)b[i].x=B[m-i]-'0'; while((1<<bit)<n+m+1)bit++; tot=1<<bit; for(int i=0;i<tot;i++)rev[i]=rev[i>>1]>>1|((i&1)<<(bit-1)); fft(a,1),fft(b,1); for(int i=0;i<tot;i++)a[i]=a[i]*b[i]; fft(a,-1); int t=0,k=0; for(int i=0;i<tot||t;i++) { t+=a[i].x/tot+0.5; res[k++]=t%10; t/=10; } while(k>1&&!res[k-1])k--; for(int i=k-1;~i;i--)cout<<res[i]; return 0; }
这篇关于3123. 高精度乘法II的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署