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)
输入描述:
The input will consist of a integer n.
输出描述:
You should output how many Shuaishuai numbers in [1...n]
示例1
输入
28
输出
1
说明
There is only one Shuaishuai number
//需要使用set做去重处理。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll num;
int a[10001];
int ind;
bool b;
set<ll> s;
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
int kk = sqrt(n);
for (int i = 2; i <= kk; i++){
b = 0;
for (int j = 2; j <= sqrt(i); j++){
if ( i%j==0 ){
b = 1;
break;
}
}
if (!b) a[ind++] = i;
}
for (int i = 0; i < ind; i++)
for (int j = 0; j < ind; j++)
for (int k = 0; k < ind; k++){
ll sum = pow(a[i], 2)+pow(a[j], 3) + pow(a[k], 4);
if (sum <= n)
{
s.insert(sum);
}
else{
break;
}
}
cout << s.size() <<endl;
return 0;
}
本文地址：https://blog.csdn.net/weixin_45465598/article/details/110713986
