[C++知识库]P1214 [USACO1.4]等差数列 Arithmetic Progressions（C/C++）

P1214 [USACO1.4]等差数列 Arithmetic Progressions

思路：暴力，把每一个双平方数都放进桶里，然后搜索即可

#include<iostream>
#include<cstdio>
#include<queue> 
#include<algorithm>
#include<vector>
using namespace std;
#define ull unsigned long long

int n,m;
bool a[250*250*2+10];//一个桶，用来存放所有双平方数；
struct data{
	int a,b;
};
data s[10010];
bool cmp(data x,data y)
{
	if(x.b==y.b)return x.a<y.a;
	return x.b<y.b;
}


int main()
{
	int count=0;
	cin >> n >> m ;
	for(int i=0;i<=m;i++)
		for(int j=0;j<=m;j++)
			a[i*i+j*j]=true;
	
	for(int i=0;i<=m*m*2;i++)
	{
		if(a[i])
		{
			for(int j=i+1;j<=m*m*2;j++)
			{
				if(a[j])
				{
					int d=j-i;
					if( ( i+(n-1)*d)>m*m*2 ) break;//等差数列最后一项如果大于上限，就跳出 
					bool f=true;
					for(int k=j+d;k<=i+(n-1)*d;k+=d)//判断等差数列每一项是否在桶里； 
					{
						if(!a[k]){
							f=false; 
							break;
						}
					}
					if(f){
						count++;
						s[count].a=i;
						s[count].b=d;
					}
				}
			}
		}
	}
	
	if(count==0){
		cout << "NONE" << endl ;
		return 0;
	}
	
	sort(s+1,s+count+1,cmp);
	for(int i=1;i<=count;i++)
		cout << s[i].a << " " << s[i].b << endl ; 		
		
    return 0;
}