题目描述
等差数列是一个形如 a,a+b,a+2b,…,a+nb 的数列,其中 n=0,1,2,3…。
在本问题中,a 是非负整数,b 是正整数。
请你编写一个程序,在双平方数集合 S 中,找到所有的长度为 n 的等差数列。
双平方数集合定义为可以被拆分为 p2+q2 的所有整数的集合(其中 p 和 q 为非负整数)。
输入格式
第一行包含整数 n,表示等差数列的长度。
第二行包含整数 m,表示 p 和 q 的上界。
输出格式
如果找不到符合条件的等差数列,则输出一行 “NONE”。
否则,输出若干行,每行包含两个整数 a,b,分别表示一个符合条件的等差数列的首项和公差。
这些行的输出,应该按 b 值从小到大排序,b 值相同的按 a 值从小到大排序,按次序输出。
数据保证满足条件的等差数列不会超过 10000 个。
数据范围
3≤n≤25,
1≤m≤250,
0≤p,q≤m
输入样例:
5
7
输出样例:
1 4
37 4
2 8
29 8
1 12
5 12
13 12
17 12
5 20
2 24
算法
枚举优化,
C++代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 250 * 250 * 2 + 10;
int n, m;
bool st[N];
struct Seq
{
int a, b;
bool operator< (const Seq& t) const
{
if (b != t.b) return b < t.b;
return a < t.a;
}
}seq[10000];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i <= m; ++i)//预生成双平方数
for (int j = i; j <= m; ++j)
st[i * i + j * j] = true;
int cnt = 0, s = m * m * 2;
for (int i = 0; i <= s; ++i)
if (st[i])//找首项
for (int j = i + 1; j <= s; ++j)
if (st[j])//找第2项
{
int d = j - i, last = i + d * (n - 1);
if (last > s) break;//优化:若末项超出范围,则终止搜索
bool flag = true;
for (int k = j + d; k <= last; k += d)
if (!st[k])//判断接下来的n-2项是否是双平方数
{
flag = false;
break;
}
if (flag) seq[cnt ++] = {i, d};//记录首项和公差
}
if (!cnt) puts("NONE");
else
{
sort(seq, seq + cnt);//按题目要求排序后输出
for (int i = 0; i < cnt; ++i)
printf("%d %d\n", seq[i].a, seq[i].b);//输出量可能较大,用printf
}
return 0;
}