P2508 [HAOI2008]圆上的整点 题解
一个奇怪的思路:
为了实现对 的降幂,我们令
。那么我们的问题就转化成了求圆
上的整点的个数。
根据坐标系,我们可以将问题转化为有多少个有序整数对 ,满足
。
众所周知,二维平面是一个很诡异的东西。因此,我们将其转化为复平面。
若复数
中的
均为整数,则此复数被称为高斯整数。
注意到 与
等价(因式分解)。因此,我们可以将这个问题再次转化为数学上的一个问题:存在多少个复数
使得其本身与其共轭复数
的乘积等于
。
那么一个整数 如何在复数域内分解呢?
我们都知道,根据唯一分解定理(算数基本定理)有,任意一个整数 在整数范围内有唯一的分解式。显然的,若我们将其中两个因子乘上
和
,那么等式依然成立。
那么同理,在高斯整数范围内,一个整数 可以表示成若干个复数因子的乘积。而其中的每个因子都在高斯整数上不能再分。这些因子,我们就可以将其叫做高斯素数。
比如:
,而
和
都不能再分了,那么这两个复数就都是高斯素数。
类似地,若我们想要在高斯整数范围内分解一个整数 ,我们就可以考虑先将
分解为若干个整数的乘积,再将其中的非高斯素数进行进一步的分解。
那我们如何判断给定的数 是不是一个高斯素数呢?
这时候费马跳出来,喊了一句:费马平方和定理!
奇素数
可以被表示成两个整数的平方和,当且仅当
可以被表示成
的形式。并且,在不考虑顺序的情况下,这个分解是唯一的。
因此:
型的素数可以被恰好分解为一对共轭复数的乘积
型的素数是高斯素数
可以被分解为
,因其分解成的两向量之间的夹角是
度,我们单独考虑它
我们记 为
型的素数,而
为
型的素数。则,
显然的,每个 都可以被分解成一对高斯素数。
继续转化:现在我们可以将原问题转化为:求出将 表示为若干对共轭复数的乘积的方案数。
先来考虑 的贡献。
对于任何一个 ,都可以被分解为
和
的乘积。对此,我们可以将
分配给
的第一个因子,
分配给
的第二个因子。不计顺序,所以有
种分配方式。
进一步考虑,我们可以发现, 一共有
种分配方式,因为我们可以给第一个因子分配
个
。
接着考虑 的贡献。
这个贡献等价于将 分成共轭的两因子的方案数。若
,则给每个因子都分配
个
。若两共轭的因子相等且虚部为
,则贡献为
。否则,为
。同理地,若只要存在一个
为奇数,则答案为
。
最后考虑 的贡献。
原来答案要乘 。当为
时,可以发现:
又因为归纳法可知, 会影响到原来的计数。因此,我们发现,我们根本就不用考虑
的贡献。
考虑原题,由于 ,所以:
综上,答案为:
最后,分解质因数,并求解。时间复杂度 。
Code: