请选择 进入手机版 | 继续访问电脑版

jzoj6065-[NOI2019模拟2019.3.18]One?One!【FFT】

[复制链接]
欣荣 发表于 2021-1-3 12:06:51 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
正题

题目链接:https://gmoj.net/senior/#main/show/6065
  题目大意

                               o                      n                      e                      n                      e                      s                      s                      (                      x                      )                          oneness(x)               oneness(x)体现                              x                          x               x的约数中全是                              1                          1               1的数的个数,给出一个长度为                              l                          l               l的随机生成的数                              n                          n               n,求                                             ∑                                       i                               =                               1                                      n                                  o                         n                         e                         n                         e                         s                         s                         (                         i                         )                              \sum_{i=1}^noneness(i)                  i=1∑n​oneness(i)
  解题思路

转换一下题意就是求                                             ∑                                       i                               =                               2                                      l                                  ⌊                                   n                                                   1                                               0                                     i                                              −                                  1                                          9                                            ⌋                         =                                   ∑                                       i                               =                               2                                      l                                  ⌊                                              9                               n                                                 1                                           0                                  i                                          −                               1                                            ⌋                              \sum_{i=2}^l\lfloor\frac{n}{\frac{10^i-1}{9}}\rfloor=\sum_{i=2}^l\lfloor\frac{9n}{10^i-1}\rfloor                  i=2∑l​⌊910i−1​n​⌋=i=2∑l​⌊10i−19n​⌋
先让                              n                          n               n乘上                              9                          9               9,然后把每一位的贡献拆成小数和整数部门,我们先来看整数部门
首先对于一个                                                 k                            ∗                            1                                       0                               i                                                      1                                       0                               j                                      −                            1                                           \frac{k*10^i}{10^j-1}               10j−1k∗10i​那么它的值应该是在第                              i                      −                      x                      j                      +                      1                      (                      x                      ∈                      N                      )                          i-xj+1(x\in N)               i−xj+1(x∈N)位会有一个                              k                          k               k。(如                                                 1                                       0                               9                                            999                              =                      1001001.001001001001001001001001                          \frac{10^9}{999}=1001001.001001001001001001001001               999109​=1001001.001001001001001001001001)
然后我们看这题,                              j                          j               j是                              1                      ∼                      n                          1\sim n               1∼n的每一个值,那么对于每第                              i                          i               i位我们拆成                              k                      ∗                      1                               0                         i                                  k*10^i               k∗10i会对第                              i                      −                      x                          i-x               i−x位产生                                       σ                         0                              (                      x                      )                          \sigma_0(x)               σ0​(x)次贡献(                                       σ                         0                              (                      x                      )                          \sigma_0(x)               σ0​(x)体现                              x                          x               x的约数个数)。设                                       a                         i                                  a_i               ai​体现第                              i                          i               i位的数,                                       f                         i                                  f_i               fi​体现第                              i                          i               i位的答案,那么有式子                                             f                            i                                  =                                   ∑                                       j                               =                               0                                      ∞                                            a                                       i                               +                               j                                                      σ                            0                                  (                         j                         )                              f_i=\sum_{j=0}^{\infty}a_{i+j}\sigma_0(j)                  fi​=j=0∑∞​ai+j​σ0​(j)
这个式子可以先预处置惩罚出                                       σ                         0                              (                      j                      )                          \sigma_0(j)               σ0​(j)然后把                              a                          a               a反过来就是一个卷积的式子,                              F                      F                      T                          FFT               FFT优化即可。
对于小数部门,因为在比力后的位数的产生贡献概率极小,又因为数字随机生成,所以我们直接将这些部门省略。我们只处置惩罚到小数的                              12                          12               12位,和上面同理算出每一个小数位的贡献即可。
时间复杂度                              O                      (                      n                      log                      ⁡                      n                      )                          O(n\log n)               O(nlogn)
                                c                      o                      d                      e                          code               code

[code]#include#include#include#include#include#define ll long longusing namespace std;const ll N=1e6+10;const double Pi=acos(-1);struct complex{    double x,y;    complex(double xx=0,double yy=0)    {x=xx;y=yy;return;}}x[N],y[N];ll n,m,r[N],a[N],d[N],b[N],f[N];unsigned int sed;complex operator+(complex x,complex y){return complex(x.x+y.x,x.y+y.y);}complex operator-(complex x,complex y){return complex(x.x-y.x,x.y-y.y);}complex operator*(complex x,complex y){return complex(x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x);}void fft(complex *f,ll op){    for(ll i=0;i
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )