P1 P2508 [HAOI2008]圆上的整点

[HAOI2008]圆上的整点

23.3.22 WE.

真是一道神题，特别是对于刚得了甲流滚回家摆烂从而有时间乱看而恰巧这几天上课刚学复数的我。

一直很好奇复数到底是什么，昨天晚上刷B站学习偶然看到了一个解释虚数的视频，结果也没看懂，只听说乘上一个 \(i\) 相当于旋转 \(90^{\circ}\) ，一想还真是！感觉挺神奇的，但又有点懵...

今天很幸运能偶然瞟了一眼，发现了这道题(貌似以前看到过好几次，但是没干出来)。

首先，讨论的都是整数。

接下来有几个概念：

(0.共轭复数)

1. 高斯整数

2. 高斯素数

都是复数的基本知识。

现在考虑题目，给出了一个 \(r \ (\leq 2e9)\) 为半径的原点圆，求多少个整点在其上。

转化一下就是求 \(a^2+b^2=r^2\) 的 \(a、b\) 个数。

这里可以引入共轭复数(高斯整数)的性质：\(z*\bar{z}=(a+bi)*(a-bi)=a^2+b^2\)

好有道理。

所以，原问题就转化为了：求有多少个高斯整数满足与其共轭复数乘积为 \(r^2\) 。

最关键的一步是在高斯整数上进行唯一分解。

同整数一样，高斯整数也存在着唯一分解式。(每个因子都不能再分)

比如 \(5=(2+i)(2-i)\) ，不能再分下去了。

而根据性质，\(-i^2=1, -1*-1=1\) ，所以上面的右式因子进行转化。即一个结果有四种方法得来：\(z \cdot \bar{z}=-z \cdot -\bar{z}=-iz \cdot i\bar{z}=iz \cdot -i\bar{z}\)

非常巧妙地对应了一个点的四象限90°旋转有4个点。

注意，此处的复数对应了坐标轴上的点(圆上的点)。(可以把点乘号前的部分看成圆上点，后面看成一个辅助运算的共轭复数(个人理解))

下面需要考虑一个定理(其实也有其它解法)：费马平方和定理。

即大于4的整数素数有这样的一个性质：

若该素数是 \(4k+1\) 的形式，则该素数一定能被唯一表达成两个数平方和。

那么 \(4k+3\) 的形式显然就不行了，所以这种素因子就只能分解成整数乘整数型。而 \(4k+1\) 形式可以分解为一对共轭复数。

有什么用呢？

考虑 \(r^2\) 的高斯素数分解：不妨另 \(N=r^2\)

有： \(N=2^n\prod_{q_i=4k+3}q_i^{m_i}\prod_{p_j=4k+1}p_j^{k_j}\)

此处特意把 \(2\) 提出来是由原因的。

不过先看后面两个，显然，问题变成了N的划分问题，把右边怎么分才能形成N，且保证划分出的都得互相是共轭复数。其中，\(q_i\) 表示 \(N\) 的高斯素数因子，这玩意是不能被分成共轭复数之积的，所以只能平分，因此对答案不做贡献(*1)，并且 \(m_i\) 一定是偶数，因为 \(N=r^2\)。而每一个 \(p_j^{k_j}\) 对答案的贡献是 \(k_j+1\) ，为什么呢？那是因为 \(p_j=z \cdot \bar{z}\) ，所以要么就把 \(z\) 给第一个因子，要么给第二个因子，所以考虑第一个因子拿到了多少个 \(z\) 即可。

现在只剩下 \(2\) 了。为什么 \(2\) 明明可以被分解成 \((i+1)(i-1)\) ，却不被考虑其贡献呢？画个图看看，发现两者实际上是成 \(90^{\circ}\)的。所以呢？所以，思考一下，如果把 \(2\) 考虑进去，那么就相当于考虑了 \((1+i)\) 和 \((1-i)\) ，相当于旋转了90°再去考虑了一个，多余了。

上面说过四种表示方式 \(z \cdot \bar{z}\) ，分别对应四个象限，所以最后的结果乘以四即可。这也说明不能考虑 \(2\) ，\(2\) 自己会率先考虑 \(2\) 个情况。

此题结了。

cin>>r;
//引入复数进行求解
for(ll i=2;i*i<=r;++i)
  if(!(r%i)){
    ll k=0;
    while(!(r%i)) ++k,r/=i;
    if(i%4==1) ans*=(k*2+1);//费马平方和定理 
  }
if(r!=1&&r%4==1) ans*=3;
cout<<ans*4<<'\n';
return 0;

okey.