欢迎光临散文网 会员登陆 & 注册

P2508 [HAOI2008]圆上的整点 题解

2022-10-03 10:44 作者:fdsji  | 我要投稿

一个奇怪的思路:

为了实现对 r 的降幂,我们令 r%5E2%20%3D%20N。那么我们的问题就转化成了求圆 x%5E2%20%2B%20y%5E2%20%3D%20N%0A 上的整点的个数。  

根据坐标系,我们可以将问题转化为有多少个有序整数对 (a%2C%20b),满足 a%5E2%20%2B%20b%5E2%20%3D%20N。  

众所周知,二维平面是一个很诡异的东西。因此,我们将其转化为复平面。

若复数 a%20%2B%20bi%0A 中的 a%2C%20b%0A 均为整数,则此复数被称为高斯整数。


注意到 a%5E2%20%2B%20b%5E2%20%3D%20N 与 (a%20%2B%20bi)(a%20-%20bi)%20%3D%20N 等价(因式分解)。因此,我们可以将这个问题再次转化为数学上的一个问题:存在多少个复数 z%0A 使得其本身与其共轭复数 %5Cbar%7Bz%7D 的乘积等于 N


那么一个整数 N 如何在复数域内分解呢?  

我们都知道,根据唯一分解定理(算数基本定理)有,任意一个整数 N 在整数范围内有唯一的分解式。显然的,若我们将其中两个因子乘上 i 和 -i,那么等式依然成立。  

那么同理,在高斯整数范围内,一个整数 N 可以表示成若干个复数因子的乘积。而其中的每个因子都在高斯整数上不能再分。这些因子,我们就可以将其叫做高斯素数。

比如:5%20%3D%20(2%20%2B%20i)(2%20-%20i),而 (2%20%2B%20i) 和 (2%20-%20i) 都不能再分了,那么这两个复数就都是高斯素数。


类似地,若我们想要在高斯整数范围内分解一个整数 N,我们就可以考虑先将 N 分解为若干个整数的乘积,再将其中的非高斯素数进行进一步的分解。


那我们如何判断给定的数  是不是一个高斯素数呢?  

这时候费马跳出来,喊了一句:费马平方和定理!  

奇素数 p 可以被表示成两个整数的平方和,当且仅当 p 可以被表示成 4k%20%2B%201 的形式。并且,在不考虑顺序的情况下,这个分解是唯一的。


因此:

  • 4k%20%2B%201 型的素数可以被恰好分解为一对共轭复数的乘积

  • 4k%20%2B%203 型的素数是高斯素数

  • 2 可以被分解为 (1%2Bi)(1-i),因其分解成的两向量之间的夹角是 90 度,我们单独考虑它


我们记 p 为 4k%20%2B%201 型的素数,而 q 为 4k%20%2B%203 型的素数。则,

N%20%3D%202%5En%20%5Cprod_%7Bp_i%20%3D%204k%20%2B%201%7D%20p_i%5E%7Bk_i%7D%20%5Cprod_%7Bq_i%20%3D%204k%20%2B%203%7D%20q_i%5E%7Bm_i%7D

显然的,每个 p_i 都可以被分解成一对高斯素数。  

继续转化:现在我们可以将原问题转化为:求出将 N 表示为若干对共轭复数的乘积的方案数。


先来考虑 p_i 的贡献。  

对于任何一个 p_i,都可以被分解为 z%5Cbar%7Bz%7D 的乘积。对此,我们可以将 z_i 分配给 N 的第一个因子,%5Cbar%7Bz%7D 分配给 N 的第二个因子。不计顺序,所以有 2 种分配方式。  

进一步考虑,我们可以发现,p_i%5E%7Bk_i%7D 一共有 k_i%20%2B%201 种分配方式,因为我们可以给第一个因子分配 0%2C%201%2C%20%5Ccdots%2C%20k_i 个 z_i


接着考虑 q_i 的贡献。  

这个贡献等价于将 q_i%5E%7Bm_i%7D 分成共轭的两因子的方案数。若 2%20%5Cmid%20m_i,则给每个因子都分配 %5Cfrac%7Bm_i%7D%7B2%7D 个 z_i。若两共轭的因子相等且虚部为 0,则贡献为 1。否则,为 0。同理地,若只要存在一个 m_i 为奇数,则答案为 0


最后考虑 2 的贡献。  

原来答案要乘 4。当为 2 时,可以发现:

(-i)(1%2Bi)%3D(1-i)

i(1-i)%3D(1%2Bi)

又因为归纳法可知,2%5Em 会影响到原来的计数。因此,我们发现,我们根本就不用考虑 2 的贡献。


考虑原题,由于 r%5E2%20%3D%20N,所以:

r%20%3D%202%5En%20%5Cprod_%7Bp_i%20%3D%204k%20%2B%201%7D%20p_i%5E%7Bk_i%7D%20%5Cprod_%7Bq_i%20%3D%204k%20%2B%203%7D%20q_i%5E%7Bm_i%7D


综上,答案为:

4%20%5Ctimes%20%5Cprod_%7Bp_i%20%3D%204k%20%2B%201%7D%20(2k_i%20%2B%201)


最后,分解质因数,并求解。时间复杂度 O(%5Csqrt%7BN%7D)


Code:



P2508 [HAOI2008]圆上的整点 题解的评论 (共 条)

分享到微博请遵守国家法律