首页 > 其他分享 >前缀素数个数的一点想法

前缀素数个数的一点想法

时间:2024-11-08 20:57:59浏览次数:4  
标签:前缀 limits ln sum 个数 sqrt 素数 inf log

前缀素数个数的一点想法

idea from pp_orange, 08/11/24

首先对于狄利克雷卷积,我们有一种视角是设 \(f(x) = \sum\limits_{i=1}^{\inf} a_{i}x^{\ln i}\),这样我们直接多项式卷积就可以干狄利克雷卷积干的事情,而且方便让多项式的性质和处理手段直接嫁接到狄利克雷卷积上来。我们约定 \(p_i\) 是第 \(i\) 个质数。

设 \(S(x) = \sum\limits_{i=1}^{\inf}x^{\ln p_i},~~~I(x) = \sum\limits_{i=1}^{\inf} x^{\ln i},~~~~P_n(x)=\sum\limits_{i=0}^{\inf}x^{i\ln p_n},~~~~\epsilon(x)=x^{\ln 0}\)

我们寻找一下这些函数之间的关系,我们希望用 \(I(x)\) 去表示 \(S(x)\)。

我们显然有:\(I(x) = \prod\limits_{i=1}^{\inf}P_i(x)\),

两边同时取 \(\ln\),得:

\[\begin{aligned} \ln I(x) &= \ln \prod\limits_{i=1}^{\inf}P_i(x) \\ &= \sum\limits_{i=1}^{\inf}\ln P_i(x)\\ &= \sum\limits_{i=1}^{\inf}\sum\limits_{j=1}^{\inf}\frac{x^{j\ln p_i}}{j}\\ &= \sum\limits_{j=1}^{\inf}\frac{1}{j}\sum\limits_{i=1}^{\inf}x^{j\ln p_i}\\ &= S(x)+\sum\limits_{j=2}^{\inf}\frac{1}{j}\sum\limits_{i=1}^{\inf}x^{j\ln p_i}\\ \end{aligned} \]

于是:

\[\begin{aligned} S(x) &= \ln I(x)-\sum\limits_{j=2}^{\inf}\frac{1}{j}\sum\limits_{i=1}^{\inf}x^{\ln p_i^j}\\ \end{aligned} \]

后面那一项都是平方以上的指数,所以数量很少(小于 \(O(\sqrt n)\)),暴力扣掉即可,于是问题转换为求解 \(\ln I(x)\)。考虑定义式:

\[\begin{aligned} \ln I(x) &= -\sum\limits_{i=1}^{\inf} \frac{(\epsilon(x)-I(x))^i}{i}\\ &= -\sum\limits_{i=1}^{\left \lfloor \log_2 n \right \rfloor} \frac{(\epsilon(x)-I(x))^i}{i}\\ \end{aligned} \]

zak 论文中的块筛卷积做到了 \(O(\sqrt n \log n \log \log n)\),而我们这个问题只需要 \(O(\log n)\) 次卷积,所以复杂度是 \(O(\sqrt n \log ^2 n \log \log n)\)。实际上进一步的,我们可以优化到 \(O(\sqrt n\log^{\frac{3}{2}}n\log \log n)\)。

我们类比古老多项式复合逆从 \(O(n^2\log n)\) 到 \(O(n^2+n\sqrt n \log n)\) 的优化路径,我们发现这个东西形式非常向复合逆,我们直接把 \((\epsilon(x)-I(x))^i\) 分解为 \((\epsilon(x)-I(x))^{ak+b}\) 的形式,其中 \(k\) 取 \(O(\sqrt {\log n})\) 级别,我们花 \(O(\sqrt n\log^{\frac{3}{2}} n\log \log n)\) 的时间把 \((\epsilon(x)-I(x))^{ak}\) 和 \((\epsilon(x)-I(x))^b\) 都处理出来,然后 \(O(\sqrt n \log n)\) 把他们组合点积到一起按照对应的系数加到一起即可。

标签:前缀,limits,ln,sum,个数,sqrt,素数,inf,log
From: https://www.cnblogs.com/pp-orange/p/18535923

相关文章

  • 代码随想录算法训练营第十五天| 110.平衡二叉树,257. 二叉树的所有路径, 404.左叶子之
    110.平衡二叉树文章链接:https://programmercarl.com/0110.平衡二叉树.html#题外话题目链接:https://leetcode.cn/problems/balanced-binary-tree/description/classSolution{public://每次都要比较左右子树的高度差是否在1以内,所以递归是要统计子树的高度的intg......
  • L1-009 N个数求和
    目录一、问题描述二、问题分析 三、源码解答四、参考资料一、问题描述本题的要求很简单,就是求N个数字的和。麻烦的是,这些数字是以有理数分子/分母的形式给出的,你输出的和也必须是有理数的形式。1.输入格式输入第一行给出一个正整数N(≤100)。随后一行按格式a1/b1a2/b......
  • cpp_9_8.9【(修改函数)计算一个数的p次幂】
    #include<stdio.h>doublepower(doublen,intp);//ANSI函数原型intmain(void){doublex,xpow;intexp;printf("Enteranumberandthepositiveintegerpower");printf("towhich\nthenumberwillberaised.Enterq......
  • 用C语言代码输出三个数
    题目:有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少?已知:1、三位数2、1-43、各不相同输出:1、有多少个这样的三位数2、依次输出#include<stdio.h>intmain(){for(intb=1;b<5;b++)  {   for(ints=1;s<5;s++)    ......
  • 子集枚举优化与高维前缀和
    前缀和与二维前缀和考虑一个序列\(a\),我们如何快速求出区间\([l,r]\)的元素和呢?这很简单,我们只需求出它的前缀和序列\(\mathrm{sum}(i)=\sum_{k=1}^ia_i\),那么答案即为\(\mathrm{sum}(r)-\mathrm{sum}(l-1)\)。而对于序列\(\mathrm{sum}\),有\(\mathrm{sum}(i)=......
  • MRP元素数据
    在开发报表的过程中,需要对MD04后边的表数据里面的不同MRP元素字段理解清楚对应的。当时比较疑惑的是关于采购订单没有和工单显示在一列而是和预留/相关需求里面的数据在同一列。去查底表RESB 发现采购申请、采购凭证、采购订单都属于预留/相关需求。MRP元素数据放的是......
  • 高维前缀和
    高维前缀和二维前缀和一般的做法是容斥:for(inti=1;i<=n;++i)for(intj=1;j<=n;++j)sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];实际上也可以固定其他维度,依次在每一维上求前缀和,即:for(inti=1;i<=n;+......
  • 数据结构 ——— 计算链式二叉树第k层的节点个数
    目录链式二叉树示意图手搓一个链式二叉树计算链式二叉树第k层的节点个数 链式二叉树示意图手搓一个链式二叉树代码演示://数据类型typedefintBTDataType;//二叉树节点的结构typedefstructBinaryTreeNode{BTDataTypedata;//每个节点的数据s......
  • MySQL 字符串索引和前缀索引
    前缀索引创建前缀索引altertabletaddindexidx_email(email);altertabletaddindexidx_email(email(6));使用前缀索引,定义好长度,可以做到即节省空间,又不用额外增加太多查询成本。区分度建立索引时,区分度(不重复的值)越高越好。selectcount(distanceemail)fromt......
  • 0基础学Python——类的单例模式、反射函数、记录类的创建个数、迭代器、生成器及生成
    0基础学Python——类的单例模式、反射函数、记录类的创建个数、迭代器、生成器及生成器练习类的单例模式定义代码演示反射函数代码演示记录类的创建个数迭代器定义特点生成器定义特点写法生成器练习生成器生成1-无穷的数字生成器生成无穷个素数类的单例模式定义......