[NC14615] Number
1
2
3
| 时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 65536K，其他语言131072K
64bit IO Format: %lld
|
题目描述
We define Shuaishuai-Number as a number which is the sum of a prime square(平方), prime cube(立方), and prime fourth power(四次方).
The first four Shuaishuai numbers are:
How many Shuaishuai numbers in [1,n]? (1<=n<=50 000 000)
输入描述
1
| The input will consist of a integer n.
|
输出描述
1
| You should output how many Shuaishuai numbers in [1...n]
|
输入
输出
说明
1
| There is only one Shuaishuai number
|
题解
题目解析
我去,我以为是什么题呢,以为用什么数学方式.结果是打表+暴力= =,蚌.
思路是用欧拉筛把素数筛出来,然后暴力枚举.然后用unique算出不重复的个数,然后直接得出答案.不过唯一我学到了一个东西就是unique()函数.
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 5e7+10;
const int PRIME = 1e5;
int a[N],prime[PRIME],visit[PRIME];
void work(){
visit[1] = 1;
for (int i = 2; i <= PRIME; i++){
if (!visit[i])
prime[++prime[0]] = i;
for (int j = 1; j <= prime[0] && i * prime[j] <= PRIME; j++){
visit[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
return ;
}
int main(){
int n,cunt=0;
work();
cin >> n;
for(int i=1;i<=PRIME;i++){
ll x = prime[i] * prime[i];
if(x >= n) break;
for(int j=1;j<=PRIME;j++){
ll y = prime[j] * prime[j] * prime[j];
if(y >= n) break;
for(int k=1;k<=PRIME;k++){
ll z = prime[k] * prime[k] * prime[k] * prime[k];
if(z >= n) break;
if(x+y+z <= n) a[cunt++] = x+y+z;
}
}
}
sort(a,a+cunt);
cout << unique(a,a+cunt) - a << endl;
return 0;
}
|
