HDU2866 Special Prime

Description

給定L,求有多少個(gè)小于L的素?cái)?shù)p，滿足方程\(n^3+p*n^2=m^3\) \(n\in Z^+,m\in Z^+\)

Input Format

輸入有多組數(shù)據(jù)，每組數(shù)據(jù)一行，每行一個(gè)正整數(shù)L。

Output Format

對于每組數(shù)據(jù)輸出一行一個(gè)正整數(shù)，表示滿足條件的素?cái)?shù)個(gè)數(shù)，若沒有滿足條件的素?cái)?shù)輸出“No Special Prime!”

Sample Input

7
777

Sample Output

1
10

Solution

引理一：\(k \in Z^+\),\((k^2+k^3)\)不是完全立方數(shù)。
證明：

假設(shè)\(k^2+k^3=a^3\)，顯然\(a>k\)

則\(k^2=a^3-k^3\)

? \(=(a-k)(a^2+a*k+k^2)\)
?
? \(\geq a^2+a*k+k^2\)

? \(>k^2\)

? 存在矛盾，故假設(shè)不成立，所以\(\forall k \in Z^+ ,(k^2+k^3)\)不是完全立方數(shù)

引理二：\(n \in Z^+ ，若n^2為完全平方數(shù)，則n也為完全平方數(shù)\)

? 證明：

? \(n^2=x^3\)

? \(n=\prod_{i=1}^k {p_i^{a_i}} ,\forall a_i \in Z^+\)

\(\because \sqrt [3] {n^2}=\prod_{i=1}^k {p_i^{\frac {2*a_i} 3}} \in Z^+\)

? \(\therefore \sqrt [3] n= \prod_{i=1}^k {p_i^{\frac {a_i} 3}\in Z^+}\)

? \(\therefore n為完全立方數(shù)\)

假設(shè)n,p不互質(zhì)，則

? \(n=p*k\)

? \(k^3*p^3+k^2+p^3=m^3\)

? \((k^2+k^3)*p^3=m^3\)

由引理一可得m不是整數(shù)，與條件矛盾，所以n與p互質(zhì)

gcd(n+p,p)=gcd(n,p)=1，所以n與n+p互質(zhì)

所以\(n^2與n+p互質(zhì)\)

又因?yàn)?span id="ze8trgl8bvbq" class="math inline">\(n^2(n+p)=m^3\)

所以\(n^2,n+p\)為完全立方數(shù)

由引理二得\(n\)也為完全立方數(shù)

設(shè)\(n=a^3,n+p=b^3\)

得\(p=b^3 -a^3\)

? \(=(b-a)(b^2 +ab+a^2)\)

因?yàn)?span id="ze8trgl8bvbq" class="math inline">\(p\)為素?cái)?shù)，所以\(b-a=1\)(因?yàn)?\(b-a\) 與 \(b^2+ab+a^2\)皆為正整數(shù)，所以兩者之中必定是一個(gè)為\(1\)一個(gè)為\(p\))

代入得\(p=3a^2+3a+1\)

所以\(Ans=\sum _{i=1}^{3i^2+3i+1 \leq L}[3i^2+3i+1為素?cái)?shù)]\)

轉(zhuǎn)載于:https://www.cnblogs.com/hyheng/p/7755827.html

總結(jié)

以上是生活随笔為你收集整理的HDU2866 Special Prime的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。