题目重现

Give you a prime number $p$, if you could find some natural number (0 is not inclusive) $n$ and $m$, satisfy the following expression:

$$n^3 + p * n^2 = m^3$$
We call this $p$ a “Special Prime”.
AekdyCoin want you to tell him the number of the “Special Prime” that no larger than $L$.
For example:
If $L = 20$
$1^3 + 7*1^2 = 2^3$
$8^3 + 19*8^2 = 12^3$

That is to say the prime number 7, 19 are two “Special Primes”.

Input

The input consists of several test cases.
Every case has only one integer indicating $L$.($1 \le L \le 10^6$)

Output

For each case, you should output a single line indicate the number of “Special Prime” that no larger than $L$. If you can’t find such “Special Prime”, just output “No Special Prime!”

Sample Input

7
777

Sample Output

1
10

题解

这是一道数论题。

对于质数$p$, 正整数$n, m$，求

$$\sum_{2 \le p \le L} [n^3+p*n^2=m^3]$$

可以导出： $n, n + p$ 一定都是完全立方数。

结论1：$n \bot p$ （n, p 互质）
假设 $n \not \bot p$，有 $n = k p, k \in Z^+$
原式化为

$$k^3p^3+k^2p^3=m^3 \\ (k^3+k^2) p^3 = m^3$$
由引理1得m不是整数，与条件矛盾！假设不成立。
所以 $n \bot p$。

因为$gcd(n, n+p) = gcd(p, n) = 1$
所以 $n \bot n + p$

所以$n^2(n + p)=m^3$中 $n, n+p$ 都是完全立方数，并且互质。

设 $n = a^3, n + p = b^3, (b > a)$
作差得：

$$\begin{align} p & = b^3 - a^3 \\ & = (b - a)(b^2+a^2+a b) \end{align}$$
因为 p 是质数，所以 $b - a = 1$，可以消去 $b$ 得：
$$p = 3a^2+3a+1, (a \in Z^+)$$

于是：

$$\sum_{2 \le p \le L} [n^3+p*n^2=m^3] = \sum_{a \gt 0, 2 \le 3a^2+3a+1 \le L} [3a^2+3a+1 \text{是质数}]$$

引理

引理1：$k\in Z^+, k^3+k^2$ 不是完全立方数

假设 $k^3+k^2 = a^3$
显然有 $a > k$

$$\begin{align} k^2 & = a^3 - k^3 \\ & = (a - k) (a^2+a k + k^2) \\ & = (a^2 - k^2) a + (a - k) k ^2 \\ & \ge (a^2 - k^2)a + k^2 \\ & \gt k^2 \end{align}$$
矛盾！假设不成立，因此对于 $k \in Z^+, k^3+k^2$ 不是完全立方数。

参考代码

• HDU 2866