一個奇怪的思路：

為了實現(xiàn)對? 的降冪，我們令 。那么我們的問題就轉(zhuǎn)化成了求圓 ?上的整點(diǎn)的個數(shù)。 ?

根據(jù)坐標(biāo)系，我們可以將問題轉(zhuǎn)化為有多少個有序整數(shù)對 ，滿足 。 ?

眾所周知，二維平面是一個很詭異的東西。因此，我們將其轉(zhuǎn)化為復(fù)平面。

若復(fù)數(shù) ?中的 ?均為整數(shù)，則此復(fù)數(shù)被稱為高斯整數(shù)。

注意到 ?與 ?等價（因式分解）。因此，我們可以將這個問題再次轉(zhuǎn)化為數(shù)學(xué)上的一個問題：存在多少個復(fù)數(shù) ?使得其本身與其共軛復(fù)數(shù) ?的乘積等于 。

那么一個整數(shù) ?如何在復(fù)數(shù)域內(nèi)分解呢？ ?

我們都知道，根據(jù)唯一分解定理（算數(shù)基本定理）有，任意一個整數(shù) ?在整數(shù)范圍內(nèi)有唯一的分解式。顯然的，若我們將其中兩個因子乘上 ?和?，那么等式依然成立。 ?

那么同理，在高斯整數(shù)范圍內(nèi)，一個整數(shù) ?可以表示成若干個復(fù)數(shù)因子的乘積。而其中的每個因子都在高斯整數(shù)上不能再分。這些因子，我們就可以將其叫做高斯素數(shù)。

比如：，而 ?和 ?都不能再分了，那么這兩個復(fù)數(shù)就都是高斯素數(shù)。

類似地，若我們想要在高斯整數(shù)范圍內(nèi)分解一個整數(shù) ，我們就可以考慮先將 ?分解為若干個整數(shù)的乘積，再將其中的非高斯素數(shù)進(jìn)行進(jìn)一步的分解。

那我們?nèi)绾闻袛嘟o定的數(shù) ?是不是一個高斯素數(shù)呢？ ?

這時候費(fèi)馬跳出來，喊了一句：費(fèi)馬平方和定理！ ?

奇素數(shù) ?可以被表示成兩個整數(shù)的平方和，當(dāng)且僅當(dāng) ?可以被表示成 ?的形式。并且，在不考慮順序的情況下，這個分解是唯一的。

因此：

• ?型的素數(shù)可以被恰好分解為一對共軛復(fù)數(shù)的乘積

• ?型的素數(shù)是高斯素數(shù)

• ?可以被分解為 ，因其分解成的兩向量之間的夾角是 ?度，我們單獨(dú)考慮它

我們記 ?為 ?型的素數(shù)，而 ?為 ?型的素數(shù)。則，

顯然的，每個 ?都可以被分解成一對高斯素數(shù)。 ?

繼續(xù)轉(zhuǎn)化：現(xiàn)在我們可以將原問題轉(zhuǎn)化為：求出將? 表示為若干對共軛復(fù)數(shù)的乘積的方案數(shù)。

先來考慮? 的貢獻(xiàn)。 ?

對于任何一個 ，都可以被分解為? 和 ?的乘積。對此，我們可以將 ?分配給 ?的第一個因子，?分配給 ?的第二個因子。不計順序，所以有 ?種分配方式。 ?

進(jìn)一步考慮，我們可以發(fā)現(xiàn)，?一共有 ?種分配方式，因為我們可以給第一個因子分配 ?個 。

接著考慮 ?的貢獻(xiàn)。 ?

這個貢獻(xiàn)等價于將 ?分成共軛的兩因子的方案數(shù)。若 ，則給每個因子都分配 ?個 。若兩共軛的因子相等且虛部為 ，則貢獻(xiàn)為 。否則，為 。同理地，若只要存在一個 ?為奇數(shù)，則答案為 。

最后考慮 ?的貢獻(xiàn)。 ?

原來答案要乘 。當(dāng)為? 時，可以發(fā)現(xiàn)：

又因為歸納法可知，?會影響到原來的計數(shù)。因此，我們發(fā)現(xiàn)，我們根本就不用考慮 ?的貢獻(xiàn)。

考慮原題，由于 ，所以：

綜上，答案為：

最后，分解質(zhì)因數(shù)，并求解。時間復(fù)雜度 。

Code: