2014
02-17

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



所以 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;
}

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