categories
OI, algorithm, USACO

An arithmetic progression is a sequence of the form a, a+b, a+2b, …, a+nb where n=0,1,2,3,… . For this problem, a is a non-negative integer and b is a positive integer.

Write a program that finds all arithmetic progressions of length n in the set S of bisquares. The set of bisquares is defined as the set of all integers of the form p2 + q2 (where p and q are non-negative integers).

## INPUTFORMAT

 Line1: N (3 <= N <= 25), the length of progressions for which to search Line2: M (1 <= M <= 250), an upper bound to limit the search to the bisquares with 0 <= p,q <= M.

## OUTPUTFORMAT

If no sequence is found, a singe line reading NONE’. Otherwise, output one or more lines, each with two integers: the first element in a found sequence and the difference between consecutive elements in the same sequence. The lines should be ordered with smallest-difference sequences first and smallest starting number within those sequences first.

There will be no more than 10,000 sequences.

## SOLUTION

1.在判断是否存在 n 个等差数时，从末尾向前判断（这个不是主要的）。

2.在枚举 list 中的数时，假设为 i,j，那么如果 list[i]+(list[j]-list[i])×(n-1)>limlim 是最大可能的 bisquare ），那么对于之后的 j 肯定也是大于 lim 的，所以直接 break 掉。（这个非常有效）

AC，最大数据1.4xs。

/*
ID:tom.tun1
PROG:ariprog
LANG:C++
*/
#include <iostream>
#include <fstream>
#include <ctime>
using namespace std;
ifstream fin("ariprog.in");
ofstream fout("ariprog.out");
int prog_len, max_num;
bool set[125001] =
{
0
};
int bsq[31375], bsq_num = 0, max_bsq;
int ans_num = 0;
{
int a;
int b;
}ans[40000];
int
cmp(const void* a, const void* b)
{
return (*(int *) a - *(int *) b);
}
int
cmp2(const void* a, const void* b)
{
if ((aa->b) != (bb->b))
return((aa->b) - (bb->b));
else
return((aa->a) - (bb->a));
}
void
check(int a, int b)/*给出首项a和公差b，检查等差数列长度并处理*/
{
for (int i = 0; i < prog_len / 2 + 1; i++)
if (!set[a + b * i] || !set[a + b * (prog_len - 1 - i)])
return;
ans[ans_num].a = a;
ans[ans_num].b = b;
ans_num++;
}
int
main()
{
fin >> prog_len >> max_num;
max_bsq = max_num * max_num * 2;
for (int p = 0; p <= max_num; p++)
for (int q = p; q <= max_num; q++)
{
int n = p* p + q* q;
if (!set[n])
{
set[n] = true;
bsq[bsq_num++] = n;
}
}
qsort(bsq, bsq_num, sizeof(bsq[0]), cmp);
for (int i = 0; i < bsq_num - prog_len + 1; i++)
for (int j = i + 1; j < bsq_num; j++)
{
int a = bsq[i], b = bsq[j] - bsq[i];
if (a + b * (prog_len - 1) > max_bsq)
break;
check(a, b);
}
if (ans_num == 0)
fout << "NONE" << endl;
else
{
qsort(ans, ans_num, sizeof(ans[0]), cmp2);
for (int i = 0; i < ans_num; i++)
fout << ans[i].a << ' ' << ans[i].b << endl;
}
return 0;
}
`