首页 > ACM题库 > HDU-杭电 > HDU 2866-Special Prime-最小生成树-[解题报告]HOJ
2014
02-17

HDU 2866-Special Prime-最小生成树-[解题报告]HOJ

Special Prime

问题描述 :

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

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”.

输入:

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

输出:

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

样例输入:

7
777

样例输出:

1
10
Hint

题目:Special Prime

题意:求范围L内满足 n^3 + p*n^2 = m^3 的素数p的个数

思路:化简一下得到 n^2 *( n + p ) = m^3 

假设 n^2 和 n+p 之间有公共素因子 p , 那么 n+p = k*p , 即 n=p*(k-1),带进去得到 p^3 * (k-1)^2 *k = m^3 , (k-1)^2*k 肯定是不能表示成某一个数的三次幂的,所以假设不成立

       所以 n^2 和 n+p 之间没有公共素因子 p , 那么可以假设n=x^3 , n+p=y^3 , 相减得到 p = y^3 – x^3 = (y-x) *(y^2+y*x+x^2) , 哈哈, p是素数,所以 y-x=1 , p =(x+1)^3 – x^3 = 3*x^2+3*x+1 , 暴力一下x,判断是否是素数就ok了

#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
#define maxn 1000010
bool prime[maxn];
void Prime()
{
    memset(prime,true,sizeof(prime));
    prime[0]=prime[1]=0;
    for(int i=2;i*i<maxn;i++)
        if(prime[i])
            for(int j=2*i;j<maxn;j+=i)
                prime[j]=0;
}
int main()
{
    Prime();
    int n,ans,p;
    while(scanf("%d",&n)!=EOF)
    {
        ans=0;
        for(int i=1;;i++)
        {
            int tmp=3*i*i+3*i+1;
            if(tmp>n)
                break;
            if(prime[tmp])
                ans++;
        }
        if(ans)
            printf("%d\n",ans);
        else
            printf("No Special Prime!\n");
    }
    return 0;
}

解题参考:http://blog.csdn.net/shiyuankongbu/article/details/9375867


  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。