首页 > 其他分享 >如何判断一个平方数?

如何判断一个平方数?

时间:2024-01-20 20:15:16浏览次数:21  
标签:平方 判断 frac log chi 如何 素数 right left

今年 SNOI2024 的有一道题的大意是算出一个序列里的哪些子区间的积是平方数.

初看来说, 判断一个数是不是平方数, 我们至少有如下三种策略.

首先我们有一个很简单, 也很精确的算法, 就是直接高精度实现 \(\lfloor\sqrt x\rfloor\), 然后看看平方回去是不是 \(x\), 通过高精度的 Newton 迭代, 这样就是 \(\tilde O(\log x)\) 的. 对于题目本身, 逐一检查就达到了 \(\tilde O(n^3\log x)\) 的时间, 但这个算法至少是多项式复杂度的.

其次, 可以用质因子的出现次数. 把每个数质因子分解, 每个出现的质因子次数都 \(\bmod 2\), 这样就可以得到一个唯一的标识, 做一个异或 hash 之后也很容易做前缀和, 但这个方法的问题是需要对 \(x\) 做质因子分解, 对于 \(x \leq 10^{36}\), 以及 \(n\) 个数都做来说是很昂贵的.

第三种方法是二次剩余. 选取一个素数 \(p\), 对于 \(p \nmid x\), 如果 Legendre 符号 \(\left(\frac{x}{p}\right)\) 的值是 \(-1\), 也即 \(x\) 模 \(p\) 下不是一个平方数, 那么 \(x\) 也不是平方数. 而且二次剩余是积性的 \(\left(\frac{xy}{p}\right) = \left(\frac{x}{p}\right)\left(\frac{y}{p}\right)\), 意味着我们也可以用前缀积来判断一个区间的积是不是二次剩余.

那么看起来就行了! 接下来是一个 直觉上正确的论证: 我们知道二次剩余在 \(\mathbb F_p^\times\) 里刚好是一半的, 所以对于一个非平方数 \(x\), 我们随机选取一个素数 \(p\), 有 \(\left(\frac{x}{p}\right) = -1\) 的概率大概是 \(1/2\), 那么我们随机选取 \(\ell\) 个素数来做 hash, 每对数就有 \(1/2^\ell\) 的概率被误判, 所以对于所有 \(O(n^2)\) 对数, 我们有误判的概率不超过 \(n^2 / 2^\ell\). 所以选取 \(O(\log n)\) 个素数, 就有很高概率不会误判了.

但是上面这个想法有很多需要细究的地方.

一个错误实现

首先让我们看现在一些常见的实现, 选取的是随机取一些 \(p\leq 10^5\) 量级的素数, 那么这个是不是对的呢... 答案是, 存在数据让这种实现有 \(100\%\) 的概率误判, 而且这种数据不算特别难造.

\(\leq 10^5\) 的素数只有不到一万个, 我们考虑对每个素数 \(q_i > 10^5\) 和 \(p_j \leq 10^5\) 打出 \(\left (\frac{q_i}{p_j}\right)\), 把这看做一个 \(\pi(10^5)\) 长的 \(\mathbb F_2\) 向量, 我们只需要取 \(\pi(10^5) + 1\) 个素数 \(q_i\), 就一定存在一个方案 \(Q = \prod_{i\in S} q_i\), 使得

\[\left (\frac{Q}{p_j}\right) = 1, \forall p_j \leq 10^5. \]

而且 \(Q\) 是正数个互异素数的乘积, 所以 \(Q\) 一定不是平方数. 它可以通过任何 \(\leq 10^5\) 的素数的二次剩余检验.

上面这个消元只需要 \(\pi(10^5)^3 / w\) 的时间, 任何一个正常的笔记本一天肯定能跑出来了.

所以我们可以看到, 至少选取 \(n\log n\) 量级以内的素数都是不够的, 我们需要让随机的范围充分大.

存在性

首先, 我们之前的证明完全只能算是一个 heuristic, 因为我们甚至没有证明 存在 一个 \(p\) 使得 \(\left(\frac{x}{p}\right) = -1\). 事实上, 证明这一点也是需要一定手段的, 我这里扩写一下 Noam Elkies 的 一个证明.

证明. 回顾 Jacobi 符号的二次互反律: 对于互素的奇数 \(n, m\), 满足

\[\left(\frac n m\right) \left(\frac m n\right) = (-1)^{\frac{n-1}{2} \frac{m-1}{2}}, \]

考虑这样一个 Dirichlet 特征 \(\chi \colon (\mathbb Z / 4x \mathbb Z) \to \{-1, 1\}\):

  • 它在 \(r\mid 2x\) 的时候都有 \(\chi(r) = 0\) (当然, 这是 Dirichlet 特征的要求之一),
  • 对于 \(r\) 和 \(2x\) 互素, 令

\[\chi(r) = \left( \frac{x}{r} \right), \]

如果 \(x\) 是奇数, 那么根据二次互反律, 有

\[\chi(r) = \left( \frac{r}{x} \right) (-1)^{\frac{x-1}{2} \frac{r-1}{2}}, \]

容易验证后者 \(\bmod 4x\) 同余的 \(r\) 是同一个值, 而且

\[\chi(a)\chi(b) = \left( \frac{ab}{x} \right) (-1)^{\frac{x-1}{2} \left(\frac{a-1}{2}+\frac{b-1}{2}\right)} = \chi(ab). \]

如果 \(x\) 是偶数, 只需证明 \(x = 4k+2\) 的情况, 根据二次互反律, 有

\[\chi(r) = \left( \frac{r}{2k+1} \right) (-1)^{k \frac{r-1}{2}} (-1)^{\frac{r^2 - 1}8}, \]

也可以验证 \(\chi(a)\chi(b) = \chi(ab)\).

此外, 设 \(x\) 的出现奇数次的质因子部分是 \(p_1\cdots p_k\), 那么

\[\chi(r) = \left(\frac x r\right) = \left(\frac {p_1} r\right) \cdots \left(\frac {p_k} r\right), \]

我们取一个 \(r_1,\dots, r_k\) 满足

\[\left(\frac {p_1} {r_1}\right) = -1, \]

其它为

\[\left(\frac {p_i} {r_i}\right) = 1, \]

这总是可以分别找到的, 然后利用中国剩余定理找到 \(r\equiv r_i \pmod {p_i}\), 就说明存在 \(\chi(r) = -1\), 所以 \(\chi\) 是非平凡的 Dirichlet 特征.

根据 \(\chi\) 的完全积性, 我们总能找到 \(\chi(p) = -1\), 这就完成了证明. \(\square\)

密度?

注意到, 上面的这个证明说了更多的一些事. 由于 \(\chi\) 是一个非平凡的 Dirichlet 特征, 所以我们有

\[\sum_{r \in (\mathbb Z / 4x \mathbb Z)^\times} \chi(r) = 0, \]

也就是说 \(1\) 和 \(-1\) 各一半.

而对于每个 \(r\), \(\{4x\cdot k + r\}_k\) 这个数列, 根据素数密度的 Dirichlet 定理, 可知其中出现的素数, 在素数里的密度是 \(1 / \phi(4x)\), 这也就说明了, 对于任意的非平方数 \(x\), 满足 \(\left(\frac x p\right) = -1\) 的素数 \(p\) 占据素数的一半.

事实上, 代数数论中有一个更加一般的定理.

Chebotarev 密度定理 的一个推论. 令 \(L\) 是数域 \(K\) 的有限 Galois 扩张, 那么 \(\mathcal O_K\) 上素理想 \(\mathfrak p\) 在 \(L/K\) 上分裂的概率是 \(1 / [L:K]\). 其中概率的具体定义是

\[\lim_{N\to \infty} \frac{\# \{ \operatorname{Norm} \mathfrak p \leq N : \mathfrak p \text{ splits} \}}{\# \{ \operatorname{Norm} \mathfrak p \leq N : \mathfrak p \}} = \frac 1{[L:K]}. \]

具体解释这每个词是什么意思还是颇费功夫的, 这里只举一个好理解的推论: 如果说 \(K=\mathbb Q\), \(L\) 是 \(n\) 次不可约多项式 \(f(x)\) 给出的分裂域, 那么素数 \(p\) 满足 \(f(x) \bmod p\) 分解成一次因子之乘积的概率为 \(1/n\).

也就是说, 当 \(x\) 是非平方数的时候, 多项式 \(f(T) = T^2 - x\) 是不可约的, 那么 \(f(T) \bmod p\) 分解成一次因子之乘积的概率是 \(1/2\), 也就是说 \(\left(\frac x p\right) = -1\) 的概率是 \(1/2\).

但是以上这些定理都是一个定性的表述, 我们仍然不知道这个 \(p\) 要关于 \(x\) 取得多么大才行. 为此, 我们还需要以下的有效版本.

有效 Chebotarev 密度定理 (Lagarias–Odlyzko) 的推论.
若对于 \(L\) 的 Dedekind \(\zeta\) 函数的广义 Riemann 假设成立, 那么设 \(\pi_L(x)\) 是 \(p\leq x\) 的满足 \(f(x)\) 分裂成一次因子之乘积的素数个数, 那么

\[\left| \pi_L(x) - \frac 1 n \operatorname{Li}(x) \right| \ll \frac 1 n \sqrt x \log(\Delta x^n) + \log \Delta, \]

其中 \(\Delta\) 是多项式 \(f(T)\) 的判别式 \(\operatorname{disc}(f)\).
这里 \(\ll\) 是 Vinogradov 记号, 是说隐藏了一个绝对常数 \(c\) (也就是说和 \(L\) 无关!)

那么对于我们的需求而言, 取 \(n=2\), 多项式 \(f(T) = T^2-A\) 的判别式的量级就是 \(\Delta = O(A)\) 的, 有

\[\left| \pi_L(x) - \frac 1 2 \operatorname{Li}(x) \right| \ll \sqrt x (\log x + \log A). \]

而我们知道, Riemann 假设成立的情况下, 素数密度也差不多是 \(|\pi(x) - \operatorname{Li}(x)| \ll \sqrt x \log x\) 的, 所以为了让选取的素数确实接近 \(1/2\) 的密度, 我们需要让波动的幅度 \(\sqrt x (\log x + \log A) = o(x / \log x)\), 这需要我们选取的范围在

\[x = \omega ( (\log A \log \log A)^2 ). \]

本题中, \(A = M^n\), 其中 \(M\) 是输入一个数的范围, \(n\) 是数组长度, 就得到了

\[x = \omega \left( (n\log M(\log n + \log\log M))^2 \right). \]

我们在这个范围内选取素数, 就能保证非平方数有 \(1/2 -o(1)\) 的概率被二次剩余筛掉了.

什么, 你说广义 Riemann 假设凭什么是对的?

标签:平方,判断,frac,log,chi,如何,素数,right,left
From: https://www.cnblogs.com/Elegia/p/17977037/square-numbers

相关文章

  • 判断当前日期是否在周范围之内
    //strs周集合,例如一、二、三、四、五、六publicstaticbooleanisWeek(Stringstrs){Calendarcalendar=Calendar.getInstance();intdayOfWeek=calendar.get(Calendar.DAY_OF_WEEK);Stringweek="";Booleanis=false;......
  • Feign源码解析6:如何集成discoveryClient获取服务列表
    背景我们上一篇介绍了feign调用的整体流程,在@FeignClient没有写死url的情况下,就会生成一个支持客户端负载均衡的LoadBalancerClient。这个LoadBalancerClient可以根据服务名,去获取服务对应的实例列表,然后再用一些客户端负载均衡算法,从这堆实例列表中选择一个实例,再进行http调用即......
  • 记录--移动端 H5 Tab 如何滚动居中
    这里给大家分享我在网上总结出来的一些知识,希望对大家有所帮助移动端H5Tab如何滚动居中Tab在PC端、移动端应用都上很常见,不过Tab在移动端比PC端更复杂。为什么呢?移动端设备屏幕较窄,一般仅能展示4~7个Item。考虑到用户体验,UI往往要求程序员实现一个功能——......
  • 动态代理IP如何选择?
    IP地址是由IP协议所提供的一种统一的地址格式,通过为每一个网络和每一台主机分配逻辑地址的方式来屏蔽物理地址的差异。根据IP地址的分配方式,IP可以分为动态IP与静态IP两种。对于大部分用户而言,日常使用的IP地址均为动态IP地址。从代理IP的角度而言,大多数用户的需求也主要是动态代理......
  • 在表格中如何实现汉字转拼音?
    Excel网络函数库自2018年发布以来,我们几乎每天都在帮助用户解决各种办公自动化问题。解决的问题多了,慢慢的我们对用户的业务场景、问题来源、困难诉求有了基本认识。为了更好的帮助大家,未来,我们将对不同职业的办公效率改善问题进行归纳总结,力求给大家推荐最佳的“效率神器”。欢迎......
  • DCDC应用电路方案中MOS管如何选型?30V60V100V150V
    MOS管在DCDC恒压/恒流电路中扮演着重要的角色。DCDC恒压电路用于将一个直流电源的电压转换为另一个恒定的电压输出。DCDC恒流电路则用于将一个直流电源的电流转换为另一个恒定的电流输出。MOS管在电路中的工作原理管在这些电路中通常用作开关元件,通过调整其栅极电压来控制导通和截......
  • 深度理解 Spring 动态数据源切换是如何实现的
    更新(不是必读,只为了帮助读者更好的理解执行过程)2022-11-16结合事务TransactionInterceptor的执行,剖析数据源是如何切换的详细分析为什么,切面要设置@Order(-9999)属性针对点一回答如下在SpringBoot项目启动的时候,会去扫描所有配置类,生成一个个的Bean,被@Transaction标记的......
  • 如何防护网站存在的sql注入攻击漏洞
    SQL注入攻击是最危险的Web漏洞之一,危害性极大,造成的后果不堪设想,因此受到了大家的高度重视。那么你知道SQL注入攻击防范方法有哪些吗?SQL注入是一种网站的攻击方法。它将SQL代码添加到网站前端GETPOST参数中,并将其传递给mysql数据库进行分析和执行语句攻击。它是一种利用应用程序......
  • spring--是如何解决单例模式下循环依赖问题的
    Spring解决单例bean的循环依赖主要依赖于容器的三级缓存机制,以及bean的提前暴露。这里是它如何工作的:三级缓存:一级缓存(singletonObjects):存储已经经过完整生命周期处理的单例bean,包括初始化和依赖注入等。二级缓存(earlySingletonObjects):存储早期的单例对象的引用,这些......
  • IP关联会怎样?如何避免多个账号的IP关联?
    当你需要运行多个账号或者多个窗口任务时,你需要关注的一个问题是多个账号是否会被关联。而引起账号关联的其中一个原因是IP关联。IP关联是什么意思?IP关联即多个账号使用同一个IP地址。比如你有多个亚马逊、Facebook账号,即使换了不同的设备,但是网络环境没有变化,仍使用的同一条IP地址......