跳到主要内容

2026

· 阅读需 1 分钟

因为是求仅由一组的平方数的和得到的数，所以我们可以很快的想到枚举区间内的所有的的平方数的和

因为值域仅为1e71e7，所以我们只需要枚举xx和yy平方做和即可在常数时间预处理完所有答案，最后遍历求合法值即可

AC代码
Details
#include<bits/stdc++.h>
using namespace std;
#define QAQ return 
#define QWQ return 0;
#define ll long long
#define pii pair< int,int >

const int N=1e7+10;

int vis[N]; 

inline void pre_work()
{
	for( int i=1;i<=sqrt( 1e7 );i++ ) for( int j=i+1;j<=sqrt( 1e7 );j++ ) if( i*i+j*j <= 1e7 ) vis[i*i+j*j]++;
}

int main()
{
//	freopen( "txt.in","r",stdin );
//	freopen( "txt.out","w",stdout );
	ios::sync_with_stdio( false );
	cin.tie( nullptr ), cout.tie( nullptr );
	pre_work();
	int n;
	cin>>n;
	vector< int > ans;
	for( int i=1;i<=n;i++ ) if( vis[i] == 1 ) ans.push_back( i );
	cout<<ans.size()<<"\n";
	for( auto &num:ans ) cout<<num<<" ";
	QWQ	  
}

时间复杂度：O(1e7)O(1e7)