本蒻蒟的第一篇题解

_OJF_ · 2020-07-07 18:06:47 · 题解

我竟然没想到我的第一篇题解是个紫题！

要是所有紫题都是这个难度就好了

来B站学数学（请先看此视频）虽然求的不是此结论，但对此题非常有用

一堆没用的截屏

先说一说本题的思路

首先是高斯质数：

我们都知道唯一分解定理，例如2250 = 2 \times 3^2 \times 5^3

但有一种特殊的数叫做高斯质数，我们来看2，它能分解为(1 + i)(1 - i)，或者说它能分解为1 ^ 2 + 1 ^ 2，同理，5能分解成2 ^ 2 + 1 ^ 2,所以它能分解成(2 + i)(2 - i)，2和5都不是高斯质数。

但3就不同了，3 = a ^ 2 + b ^ 2 没有整数解，所以它是高斯质数。还有刚才分解出来的(1 + i)，(1 - i)，(2 + i)，(2 - i)等除了乘i，-i或-1以外没有以上的分解方式，它们也是高斯质数。

在视频里说的是关于r ^ 2的分解，但在这里r是正整数，所以在视频中有没有解的情况，而这里没有。

视频中还解释了为什么每个非高斯质数也不是2的相同的质因子能为乘积提供个数+ 1

视频中还解释了为什么质因子2虽不是高斯质数但不能为乘积提供任何变化以及为什么要\times 4。

以半径为5做例

最后cnt变量还需要乘2再加1,这个不用说明，现在上代码吧：

#include<bits/stdc++.h>
using namespace std;
bool isp(long long a)//判断质数，不用多说
{
    for(int i = 2;i <= sqrt(a) + 0.1;i++)
        if(a % i == 0)
            return false;
    return true;
}
int n, ans = 4, cnt;//ans = 4省去乘$4$这一步，cnt可以使用很多次，n就是 $r$
int main()
{
    cin>>n;
    while(n % 2 == 0)
    {
        n /= 2;
    }//根据视频所说，把质因子2全去了
    int q = sqrt(n) + 0.1;//这样就只会剩下一个质数或者1了，还不会TLE，岂不美哉？
    for(int i = 3;i <= 2 * q;i += 2)
    {
        cnt = 0;
        if(i % 4 == 3)//直接判断高斯质数
        {
            while(n % i == 0)
            {
                n /= i;
            }
        } else {
            while(n % i == 0)
            {
                n /= i;
                cnt++;
            }
            ans *= cnt * 2 + 1;//注意视频里是平方后的结论，所以先*2，再+1
        }
    }
    if(n != 1)//可能会留下一个质因子，判断其是否是高斯质数
    {
        if(n % 4 == 1) 
        {
            ans *= 3;//乘上1*2+1
        }
    }
    cout<<ans;
    return 0;
}

这篇题解就到这里了，希望管理员给过！