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

P6222 简单题加强版——各种推式子trick大杂烩

[复制链接]
卓小兔 发表于 2021-1-1 18:32:10 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
文章目次



Description

求                                             ∑                                       i                               =                               1                                      n                                            ∑                                       j                               =                               1                                      n                                  (                         i                         +                         j                                   )                            t                                            μ                            2                                  (                         gcd                         ⁡                         (                         i                         ,                         j                         )                         )                         gcd                         ⁡                         (                         i                         ,                         j                         )                              \sum_{i=1}^n \sum_{j=1}^n (i+j)^t \mu^2(\gcd(i,j)) \gcd(i,j)                  i=1∑n​j=1∑n​(i+j)tμ2(gcd(i,j))gcd(i,j)
                               q                          q               q组询问,                              t                          t               t为常量,                              n                          n               n为变量。每个答案都要对                                       2                         32                                  2^{32}               232取模。                              n                      ≤                      1                               0                         7                              ,                      q                      ≤                      1                               0                         4                                  n≤10^7,q≤10^4               n≤107,q≤104。
时间限制                                   0.5                         s                         −                         1.5                         s                              0.5s-1.5s                  0.5s−1.5s,空间限制256MB
Solution

Part 1: 莫反推式子

一道比力套路的推式子题,中间用到了许多推式子的trick。
                                              ∑                                       i                               =                               1                                      n                                            ∑                                       j                               =                               1                                      n                                  (                         i                         +                         j                                   )                            t                                            μ                            2                                  (                         gcd                         ⁡                         (                         i                         ,                         j                         )                         )                         gcd                         ⁡                         (                         i                         ,                         j                         )                              \sum_{i=1}^n \sum_{j=1}^n (i+j)^t \mu^2(\gcd(i,j)) \gcd(i,j)                  i=1∑n​j=1∑n​(i+j)tμ2(gcd(i,j))gcd(i,j)
                                    =                                   ∑                                       k                               =                               1                                      n                                            μ                            2                                  (                         k                         )                                                   k                                                             ∑                                       i                               =                               1                                      n                                            ∑                                       j                               =                               1                                      n                                  [                         gcd                         ⁡                         (                         i                         ,                         j                         )                         =                         k                         ]                         (                         i                         +                         j                                   )                            t                                       =\sum_{k=1}^n \mu^2(k)\ k\ \sum_{i=1}^n \sum_{j=1}^n [\gcd(i,j)=k] (i+j)^t                  =k=1∑n​μ2(k) k i=1∑n​j=1∑n​[gcd(i,j)=k](i+j)t
                                    =                                   ∑                                       k                               =                               1                                      n                                            μ                            2                                  (                         k                         )                                                             k                                       t                               +                               1                                                                                ∑                                       i                               =                               1                                                 ⌊                                           n                                  k                                          ⌋                                                      ∑                                       j                               =                               1                                                 ⌊                                           n                                  k                                          ⌋                                            [                         gcd                         ⁡                         (                         i                         ,                         j                         )                         =                         1                         ]                         (                         i                         +                         j                                   )                            t                                       =\sum_{k=1}^n \mu^2(k)\ k^{t+1}\ \sum_{i=1}^{\lfloor \frac n k \rfloor} \sum_{j=1}^{\lfloor \frac n k \rfloor} [\gcd(i,j)=1] (i+j)^t                  =k=1∑n​μ2(k) kt+1 i=1∑⌊kn​⌋​j=1∑⌊kn​⌋​[gcd(i,j)=1](i+j)t
                                    =                                   ∑                                       k                               =                               1                                      n                                            μ                            2                                  (                         k                         )                                                             k                                       t                               +                               1                                                                                ∑                                       i                               =                               1                                                 ⌊                                           n                                  k                                          ⌋                                                      ∑                                       j                               =                               1                                                 ⌊                                           n                                  k                                          ⌋                                            (                                   ∑                                       d                               ∣                               g                               c                               d                               (                               i                               ,                               j                               )                                            μ                         (                         d                         )                         )                                                   (                         i                         +                         j                                   )                            t                                       =\sum_{k=1}^n \mu^2(k)\ k^{t+1}\ \sum_{i=1}^{\lfloor \frac n k \rfloor} \sum_{j=1}^{\lfloor \frac n k \rfloor} (\sum_{d|gcd(i,j)} \mu(d))\ (i+j)^t                  =k=1∑n​μ2(k) kt+1 i=1∑⌊kn​⌋​j=1∑⌊kn​⌋​(d∣gcd(i,j)∑​μ(d)) (i+j)t
                                    =                                   ∑                                       k                               =                               1                                      n                                            μ                            2                                  (                         k                         )                                                             k                                       t                               +                               1                                                                                ∑                                       d                               =                               1                                                 ⌊                                           n                                  k                                          ⌋                                            μ                         (                         d                         )                                                             d                            t                                                            (                                   ∑                                       i                               =                               1                                                 ⌊                                           n                                               k                                     d                                                      ⌋                                                      ∑                                       j                               =                               1                                                 ⌊                                           n                                               k                                     d                                                      ⌋                                            (                         i                         +                         j                                   )                            t                                  )                         )                              =\sum_{k=1}^n \mu^2(k)\ k^{t+1}\ \sum_{d=1}^{\lfloor \frac n k \rfloor} \mu(d)\ d^{t}\ (\sum_{i=1}^{\lfloor \frac n {kd} \rfloor} \sum_{j=1}^{\lfloor \frac n {kd} \rfloor} (i+j)^t))                  =k=1∑n​μ2(k) kt+1 d=1∑⌊kn​⌋​μ(d) dt (i=1∑⌊kdn​⌋​j=1∑⌊kdn​⌋​(i+j)t))
令                              F                      (                      x                      )                      =                               ∑                                   i                            =                            1                                  x                                       ∑                                   j                            =                            1                                  x                              (                      i                      +                      j                               )                         f                                  F(x)=\sum_{i=1}^x \sum_{j=1}^x (i+j)^f               F(x)=∑i=1x​∑j=1x​(i+j)f,带入得
                                              ∑                                       k                               =                               1                                      n                                            μ                            2                                  (                         k                         )                                                             k                                       t                               +                               1                                                                                ∑                                       d                               =                               1                                                 ⌊                                           n                                  k                                          ⌋                                            μ                         (                         d                         )                                                             d                            t                                                            F                         (                         ⌊                                   n                                       k                               d                                            ⌋                         )                              \sum_{k=1}^n \mu^2(k)\ k^{t+1}\ \sum_{d=1}^{\lfloor \frac n k \rfloor} \mu(d)\ d^{t}\ F(\lfloor \frac n {kd} \rfloor)                  k=1∑n​μ2(k) kt+1 d=1∑⌊kn​⌋​μ(d) dt F(⌊kdn​⌋)
令                              T                      =                      k                      d                          T=kd               T=kd,转而枚举                              T                          T               T并将枚举                              T                          T               T的                              ∑                          \sum               ∑提到最外层,
                                              ∑                                       T                               =                               1                                      n                                  F                         (                         ⌊                                   n                            T                                  ⌋                         )                                                             ∑                                       k                               ∣                               T                                                      μ                            2                                  (                         k                         )                                   k                                       t                               +                               1                                            μ                         (                                   T                            k                                  )                         (                                   T                            k                                            )                            t                                       \sum_{T=1}^n F(\lfloor \frac n T \rfloor)\ \sum_{k|T} \mu^2(k) k^{t+1} \mu(\frac T k) (\frac T k)^{t}                  T=1∑n​F(⌊Tn​⌋) k∣T∑​μ2(k)kt+1μ(kT​)(kT​)t
                                    =                                   ∑                                       T                               =                               1                                      n                                  F                         (                         ⌊                                   n                            T                                  ⌋                         )                                                             T                            k                                                                      ∑                                       k                               ∣                               T                                                      μ                            2                                  (                         k                         )                         k                                                   μ                         (                                   T                            k                                  )                              =\sum_{T=1}^n F(\lfloor \frac n T \rfloor)\ T^k\ \sum_{k|T} \mu^2(k) k\ \mu(\frac T k)                  =T=1∑n​F(⌊Tn​⌋) Tk k∣T∑​μ2(k)k μ(kT​)
令                              G                      (                      T                      )                      =                               T                         k                                       ∑                                   k                            ∣                            T                                                μ                         2                              (                      k                      )                      k                                             μ                      (                               T                         k                              )                          G(T)=T^k \sum_{k|T} \mu^2(k) k\ \mu(\frac T k)               G(T)=Tk∑k∣T​μ2(k)k μ(kT​),带入得
                                              ∑                                       T                               =                               1                                      n                                  F                         (                         ⌊                                   n                            T                                  ⌋                         )                                                   G                         (                         T                         )                              \sum_{T=1}^n F(\lfloor \frac n T \rfloor)\ G(T)                  T=1∑n​F(⌊Tn​⌋) G(T)
这不是卷积形式吗 可以发现这是一个整除分块的套路式。现在我们只需要快速求出单个                              F                          F               F以及一个区间的                              G                          G               G之和即可,而后者可以通过前缀和求出。所以现在我们只需要思考如何快速求出                              F                      ,                      G                          F,G               F,G函数。
Part 2: 求函数F

先思量                              F                      (                      n                      )                          F(n)               F(n)。
                                              ∑                                       i                               =                               1                                      n                                            ∑                                       j                               =                               1                                      n                                  (                         i                         +                         j                                   )                            f                                       \sum_{i=1}^n \sum_{j=1}^n (i+j)^f                  i=1∑n​j=1∑n​(i+j)f
思量去枚举                              i                      +                      j                          i+j               i+j。对于一个                              (                      i                      +                      j                      )                      =                      s                      u                      m                          (i+j)=sum               (i+j)=sum它的贡献是                              s                      u                               m                         k                                                              p                                   s                            u                            m                                           sum^k\ p_{sum}               sumk psum​,此中                                       p                                   s                            u                            m                                           p_{sum}               psum​体现任选两个在                              [                      1                      ,                      n                      ]                          [1,n]               [1,n]区间内的整数使得它们的和恰好为                              s                      u                      m                          sum               sum的方案数。
先思量如何求出                                       p                                   s                            u                            m                                           p_{sum}               psum​。分类讨论:
①若                              s                      u                      m                      ≤                      n                          sum≤n               sum≤n,那么                                       p                                   s                            u                            m                                       =                      s                      u                      m                      −                      1                          p_{sum}=sum-1               psum​=sum−1;
②否则                                       p                                   s                            u                            m                                       =                      2                      n                      −                      s                      u                      m                      +                      1                          p_{sum}=2n-sum+1               psum​=2n−sum+1。
我们枚举                              s                      u                      m                          sum               sum(即下式中的                              i                          i               i):
                                              ∑                                       i                               =                               1                                      n                                  (                         i                         −                         1                         )                                   i                            k                                  +                                   ∑                                       i                               =                               n                               +                               1                                                 2                               n                                            (                         2                         n                         −                         i                         +                         1                         )                                                             i                            k                                       \sum_{i=1}^n (i-1)i^k+\sum_{i=n+1}^{2n} (2n-i+1)\ i^k                  i=1∑n​(i−1)ik+i=n+1∑2n​(2n−i+1) ik
                                    =                         (                                   ∑                                       i                               =                               1                                      n                                            ∑                                       j                               =                                           i                                  +                                  1                                                 n                                            j                            k                                  )                         +                         (                                   ∑                                       i                               =                               n                               +                               1                                                 2                               n                                                      ∑                                       j                               =                               n                               +                               1                                      i                                            j                            k                                  )                              =(\sum_{i=1}^n \sum_{j={i+1}}^n j^k)+(\sum_{i=n+1}^{2n} \sum_{j=n+1}^i j^k)                  =(i=1∑n​j=i+1∑n​jk)+(i=n+1∑2n​j=n+1∑i​jk)
令                              S                      (                      x                      )                      =                               ∑                                   i                            =                            1                                  x                                       i                         f                                  S(x)=\sum_{i=1}^x i^f               S(x)=∑i=1x​if,带入得
                                    (                                   ∑                                       i                               =                               1                                      n                                  S                         (                         n                         )                         −                         S                         (                         i                         )                         )                         +                                   ∑                                       i                               =                               n                               +                               1                                                 2                               n                                                                      S                         (                         i                         )                         −                         S                         (                         n                         )                              (\sum_{i=1}^n S(n)-S(i))+\sum_{i=n+1}^{2n}\ S(i)-S(n)                  (i=1∑n​S(n)−S(i))+i=n+1∑2n​ S(i)−S(n)
                                    =                         n                         S                         (                         n                         )                         −                                   ∑                                       i                               =                               1                                      n                                  S                         (                         i                         )                         +                                   ∑                                       i                               =                               n                               +                               1                                                 2                               n                                                                      S                         (                         i                         )                         −                         n                         S                         (                         n                         )                              =nS(n)-\sum_{i=1}^n S(i)+\sum_{i=n+1}^{2n}\ S(i)-nS(n)                  =nS(n)−i=1∑n​S(i)+i=n+1∑2n​ S(i)−nS(n)
                                    =                                   ∑                                       i                               =                               n                               +                               1                                                 2                               n                                            S                         (                         i                         )                         −                                   ∑                                       i                               =                               1                                      n                                  S                         (                         i                         )                              =\sum_{i=n+1}^{2n} S(i)-\sum_{i=1}^n S(i)                  =i=n+1∑2n​S(i)−i=1∑n​S(i)
                                    =                         (                                   ∑                                       i                               =                               1                                                 2                               n                                            S                         (                         i                         )                         −                                   ∑                                       i                               =                               1                                      n                                  S                         (                         i                         )                         )                         −                                   ∑                                       i                               =                               1                                      n                                  S                         (                         i                         )                              =(\sum_{i=1}^{2n} S(i)-\sum_{i=1}^n S(i))-\sum_{i=1}^n S(i)                  =(i=1∑2n​S(i)−i=1∑n​S(i))−i=1∑n​S(i)
令                                       S                         ′                              (                      x                      )                      =                               ∑                                   i                            =                            1                                  x                              S                      (                      i                      )                          S'(x)=\sum_{i=1}^x S(i)               S′(x)=∑i=1x​S(i),带入得
                               F                      (                      n                      )                      =                               S                         ′                              (                      2                      n                      )                      −                      2                      S                      (                      n                      )                          F(n)=S'(2n)-2S(n)               F(n)=S′(2n)−2S(n)
于是我们对                              S                          S               S做两遍前缀和处置处罚即可                              O                      (                      1                      )                          O(1)               O(1)调用求出                              F                          F               F。
注意                              S                          S               S可以通过积性筛预处置处罚求出来。
Part 3: 求函数G

观察一下:                                   G                         (                         T                         )                         =                                   ∑                                       k                               ∣                               T                                                      μ                            2                                  (                         k                         )                         k                                                   μ                         (                                   T                            k                                  )                              G(T)=\sum_{k|T} \mu^2(k) k\ \mu(\frac T k)                  G(T)=k∣T∑​μ2(k)k μ(kT​)
可以发现,这个函数是由许多积性函数(                              i                      d                      ,                      μ                          id,\mu               id,μ)组成的。所以                              G                          G               G自己也是一个积性函数,所以可以思量线性筛积性函数
线性筛积性函数只需要思考一种情况即可得到一般的筛法。这就是                              T                      =                               p                         c                                  T=p^c               T=pc的情况,此中                              p                          p               p为质数且                              c                          c               c为自然数。
①                              c                      =                      0                          c=0               c=0: 此时                              T                      =                      1                          T=1               T=1,                              G                      (                      T                      )                      =                      1                          G(T)=1               G(T)=1;
②                              c                      =                      1                          c=1               c=1: 此时
                                    G                         (                         T                         )                         =                                   μ                            2                                  (                         1                         )                         ×                         1                         ×                         μ                         (                         T                         )                         +                                   μ                            2                                  (                         T                         )                         ×                         T                         ×                         μ                         (                         1                         )                              G(T)=\mu^2(1)×1×\mu(T)+\mu^2(T)×T×\mu(1)                  G(T)=μ2(1)×1×μ(T)+μ2(T)×T×μ(1)
即在这种情况中                              G                      (                      T                      )                      =                      T                      −                      1                          G(T)=T-1               G(T)=T−1。
③                              c                      =                      2                          c=2               c=2: 显然只有                                       μ                         2                              (                      p                      )                      ×                      p                      ×                      μ                      (                      p                      )                          \mu^2(p)×p×\mu(p)               μ2(p)×p×μ(p)能产生非                              0                          0               0的贡献,而这个值即是                              1                      ×                      p                      ×                      (                      −                      1                      )                      =                      −                      p                          1×p×(-1)=-p               1×p×(−1)=−p,所以                              G                      (                      T                      )                      =                      −                      p                          G(T)=-p               G(T)=−p
④当                              c                      ≥                      3                          c≥3               c≥3时,对于任意满足                              u                      +                      v                      =                      c                          u+v=c               u+v=c的正整数对                              (                      u                      ,                      v                      )                          (u,v)               (u,v)都存在                              u                      >                      1                          u>1               u>1或                              v                      >                      1                          v>1               v>1,而任何质数的凌驾                              1                          1               1次方的莫比乌斯函数值都是                              0                          0               0,所以此时                              G                      (                      T                      )                      =                      0                          G(T)=0               G(T)=0。
  为什么说思量了                              T                      =                               p                         c                                  T=p^c               T=pc的情况之后就完全搞定了这种函数的积性筛呢?我们看一下                              G                          G               G的线性筛的代码:
[code]//judge记载了这个数是否为合数for (int i=2;i>1,x*=x)          if (y&1)  res*=x;        return res;}void init(){        pre_k[1]=1,f[1]=1;        for (int i=2;ilen>>k;len*=2;        init();        while (t--){                cin>>n;ans=0;                for (int l=1,r;l
回复

使用道具 举报

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

本版积分规则


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

18768367769

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

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

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