【传送门:BZOJ2179&caioj1450


简要题意:

  给出两个超级大的整数,求出a*b


题解:

  Rose_max出的一道FFT例题,卡掉高精度 = =(没想到BZOJ也有)

  只要把a和b的每一位当作是多项式的系数,然后做FFT就好了

  然后将答案取下来,进行进位的操作,最后输出就好了


参考代码:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const double PI=acos(-1.0);
struct Complex
{
double r,i;
Complex(){}
Complex(double _r,double _i){r=_r;i=_i;}
friend Complex operator + (const Complex &x,const Complex &y){return Complex(x.r+y.r,x.i+y.i);}
friend Complex operator - (const Complex &x,const Complex &y){return Complex(x.r-y.r,x.i-y.i);}
friend Complex operator * (const Complex &x,const Complex &y){return Complex(x.r*y.r-x.i*y.i,x.i*y.r+x.r*y.i);}
}a[],b[];
int n,m;
int R[];
void fft(Complex *y,int len,int on)
{
for(int i=;i<len;i++) if(i<R[i]) swap(y[i],y[R[i]]);
for(int i=;i<len;i<<=)
{
Complex wn(cos(PI/i),sin(on*PI/i));
for(int j=;j<len;j+=(i<<))
{
Complex w(,);
for(int k=;k<i;k++,w=w*wn)
{
Complex u=y[j+k];
Complex v=w*y[j+k+i];
y[j+k]=u+v;
y[j+k+i]=u-v;
}
}
}
if(on==-) for(int i=;i<len;i++) y[i].r/=len;
}
void calc()
{
m+=n;
int L=;
for(n=;n<=m;n<<=) L++;
for(int i=;i<n;i++) R[i]=(R[i>>]>>)|(i&)<<(L-);
fft(a,n,);
fft(b,n,);
for(int i=;i<=n;i++) a[i]=a[i]*b[i];
fft(a,n,-);
}
char st[];
int d[];
int main()
{
scanf("%s",st+);
n=strlen(st+);n--;
for(int i=;i<=n;i++) a[i].r=double(st[i+]-'');
scanf("%s",st+);
m=strlen(st+);m--;
for(int i=;i<=m;i++) b[i].r=double(st[i+]-'');
calc();
for(int i=;i<=m;i++) d[i]=int(a[m-i].r+0.5);
for(int i=;i<=m;i++)
{
d[i+]+=d[i]/;
d[i]%=;
}
int i=m;
while(d[i+]!=)
{
i++;
d[i+]+=d[i]/;
d[i]%=;
}
m=i;
for(int i=m;i>=;i--) printf("%d",d[i]);
printf("\n");
return ;
}

最新文章

  1. HTTP 头字段总结
  2. C# socket通信
  3. sprintf、fprintf和printf这三个函数
  4. 处理滚动条置底的JS代码
  5. iOS 开发 证书总结 开发证书和生产证书的区别
  6. 内部技术分享的 PPT
  7. 5 输出的properties文件按照key进行排序
  8. sqlserver 经典入门基础书籍
  9. Java的进制转换操作(十进制、十六进制、二进制)
  10. 第二章:JavaScript对象
  11. jQuery 对AMD的支持(Require.js中如何使用jQuery)
  12. 解决:sudo: pip: command not found
  13. 解决eureka注册时使用ip而不是hostname
  14. 微信小程序——获取用户unionId
  15. linux 常用 掌握要点 详细终结
  16. MySql数据库 sql查询增加序号的伪列
  17. idea导入maven项目,包没有自动下载
  18. ubuntu18.04下安装Anaconda及numpy、matplotlib
  19. js实现点击评论进行显示回复框
  20. 多线程-定时器Timer

热门文章

  1. UVA 11404 Palindromic Subsequence
  2. 简单谈谈MySQL优化利器-慢查询
  3. 洛谷—— P1640 [SCOI2010]连续攻击游戏
  4. ORACLE-014:oracle中查看DBLinkpassword
  5. BCB使用线程删除目录中的图片
  6. NOIP2017提高组模拟赛4 (总结)
  7. Java 7之传统I/O - 字符类 StringReader和StringWriter
  8. Web开发中 前端路由 实现的几种方式和适用场景
  9. Android tablayout增加选择tab 的事件.
  10. RocketMQ学习笔记(8)----RocketMQ的Producer API简介