题解 P2508 【[HAOI2008]圆上的整点】

· · 题解

首先我依然要推一下这个视频：->Click\ Here<-

当初看不懂这个视频，现在依然看不大懂……但还是懂一点了……

我这里就只说说结论了……

（按视频的内容，我们要把R转换成\sqrt{R^2}来看，这样）

[FBI WARNING] 下方及其混乱 纯属个人理解 并不严谨

前置芝士（瞎讲）

首先我们知道，一个平面直角坐标系是看成全体复数的集合的，(x,y)就可以用x+yi\ \ (i=\sqrt{-1})表示。

举个栗子，比如(3,4)这个点，在复数平面上就是3+4i。

其次，我们知道，一个整点如果在圆上，要满足的是x^2+y^2=r^2，比如3^2+4^2=5^2。

我们将3^2+4^2=25这个式子进行因式分解，会发现3^2+4^2=(3+4i)(3-4i)，(3-4i)就称为(3+4i)的“复共轭”（即实数部相等 复数部为相反数的两个复数）。

重要的来了，此时我们会发现，有一些素数，它们的平方可以被因式分解成一个复数和这个复数的复共轭的乘积，如 5^2=25=(3+4i)(3-4i)，13^2=169=(5+12i)(5-12i)，经过找规律，我们可以发现这些素数 mod\ 4=1，而且以它们为半径的圆总是经过(1+4)\times 4=20个点，这些素数就是我们解题的关键了。

事实上素数可以分为三种：2、“高斯素数”和其他素数，高斯素数的特征就是mod\ 4=3，而高斯素数的定义是无法被分解成两个复数的乘积的数。对于一个素数来说，这意味着什么呢？很明显，它的平方无法用两个数的平方和表示，也就是说以它为半径的圆除去坐标轴外没有任何一个整点。

解题方法

对于这题，我们先将R分解质因数：

R=\prod_{i=1}^{n} p_i^{k_i}\ \ p_i\in Prime

然后答案就等于：

ans=(\prod_{i=1}^{n}k_i\times 2+1\ \ p_i\in \{x\ |\ x\ mod\ 4=1 \ \ x\in Prime\})\times 4

解释一下为什么，如果一个质因数对答案有贡献，首先它得是mod\ 4=1的素数，即非2、非“高斯素数”，然后因为我们是把R当成\sqrt{R^2}来看的，在分解时每个k_i会被分解成k_i\times 2，然后最后加上的1代表着坐标轴上的点，这是一个象限的点的总和，所以最后将它乘上4即可

于是这道题的解法就呼之欲出了，当然，为了节省空间，防止MLE和TLE，我们在筛的时候只筛到了\sqrt R，这时我们要防止一种事情的发生，也就是说R可能等于一个素数\times 2或者它本身就是一个素数（因为这样它的质因数才能大于\sqrt R），所以最后判一下R是否为1，不是的话再判断它是否为高斯素数，如果仍不是，则需要将答案乘上(1\times 2+1)（因为此时的ki只可能为1）。

（非常混乱 凑合着看吧 感觉Bug应该挺多的）

见代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int r,n,pri[100005],tot;
ll ans=1;
bool isp[500005];
int main()
{
    scanf("%d",&r);
    n=sqrt(r);
    for(int i=2;i<=n;i++)
    {
        if(!isp[i]) pri[++tot]=i;
        for(int j=1;j<=tot && i*pri[j]<=n;j++)
        {
            isp[i*pri[j]]=1;
            if(!(i%pri[j])) break;
        }
    }
    for(int i=1;i<=tot;i++)
    {
        int sum=0;
        while(!(r%pri[i]))
        {
            sum++;
            r/=pri[i];
        }
        if(pri[i]%4==1) ans*=sum*2+1;
    }
    if(r>1 && r%4==1) ans*=3;
    printf("%lld\n",ans*4);
    return 0;
}