将Shuaishuai数定义为一个数,它是一个质数的平方、立方和四次方的和。
前四个Shuaishuai数是:
在[1,n]范围内有多少个Shuaishuai数?(1<=n<=50 000 000)
输入描述:
输入将由一个整数n组成。
输出描述:
您应该输出[1...n]范围内有多少个Shuaishuai数。
#include<bits/stdc++.h> using namespace std; const int N = 84,K = 5e7; int p[N],cnt,ans; bool st[N]; //84^2+84^3+84^4 = 50386896 void init(){ for(int i=2; i<=N; i++){ if(!st[i]) p[cnt++] = i; for(int j=0; p[j]<=N/i; j++){ st[p[j]*i] = true; if(i%p[j]==0) break; } } } int main() { // int a = 84*84; // cout<<a+a*84+a*a; int n; cin>>n; init(); for(int i=0; i<cnt; i++){ int a = p[i]*p[i]; if(a>=n) continue; for(int j=0; j<cnt; j++){ int b = p[j]*p[j]*p[j]; if(a+b>=n) continue; for(int k=0; k<cnt; k++){ int c = p[k]*p[k]*p[k]*p[k]; if(a+b+c<=n) ans++; } } } cout<<ans; return 0; }
一开始误以为一个质数的平方、立方和四次方的和是最大的,即a^2 + b^3 + c^4中a、b、c取同一个数。
所以通过84^2+84^3+84^4 = 50386896以为质数存到八十多就够了。
实际上也可以一个很小的数的平方加上大数的立方或四次方。因此质数应该重新找出可能的最大质数。
然后又通过150^4 = 506,250,000认为最大到150就够了,实际上还是错误的。
对于题目要求a^2 + b^3 + c^4 <= 50 000 000,应该求出a、b、c所有可能取值的质数,所以应该从a入手,因此最大质数应该接近sqrt(50 000 000)。
下面是修改后的正确解法:
#include<bits/stdc++.h> using namespace std; //sqrt(50 000 000) = 7071 const int N = 7072,K = 5e7; //150^4 = 506,250,000 vector<int> p; bool st[N]; //84^2+84^3+84^4 = 50386896 unordered_set<int> S; void init(int n){ for(int i=2; i<=n; i++){ if(!st[i]) p.push_back(i); for(int j=0; p[j]<=n/i; j++){ st[p[j]*i] = true; if(i%p[j]==0) break; } } } int main() { // int a = 84*84; // cout<<a+a*84+a*a; int n; cin>>n; init(sqrt(n)); int cnt = p.size(); for(int i=0; i<cnt; i++){ int a = pow(p[i],2); if(a>=n) break; for(int j=0; j<cnt; j++){ int b = pow(p[j],3); if(a+b>=n) break; for(int k=0; k<cnt; k++){ int c = pow(p[k],4); if(a+b+c>n) break; S.insert(a+b+c); } } } cout<<S.size(); return 0; }
全部评论
(1) 回帖