USACO 1.4 - Arithmetic Progressions

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 p² + q² (where p and q are non-negative integers).

TIME LIMIT: 5 secs

PROGRAM NAME: ariprog

INPUT FORMAT

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

SAMPLE INPUT (file ariprog.in)

5
7

OUTPUT FORMAT

If no sequence is found, a single 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.

SAMPLE OUTPUT (file ariprog.out)

1 4
37 4
2 8
29 8
1 12
5 12
13 12
17 12
5 20
2 24

출처: http://train.usaco.org/

등차수열이란 첫 항부터 차례로 일정한 수를 더하여 얻어지는 수열으로써 a, a+b, a+2b, ..., a+nb where n=0,1,2,3,... 으로 표현할 수 있다.

이 문제에서는 a는 음수가 아닌 수 이고 b는 양수이다.

이 때, bisquares이라는 집합에 속하는 길이가 n(3 <= N <= 25)인 모든 등차수열을 찾는 프로그램을 작성하라.

bisquares 집합은 p^2+q^2(0 <= p,q <= M )으로 표현 되는 모든 정수의 집합이라 정의한다.

시간 복잡도를 줄이는 것이 중요한 문제로써 미리 bisquares 집합을 구해놓는 것이 유리합니다.

그 이외에는 naive 하게 풀었는데 더 좋은 해법이 있을 것 같네요...

my solving

c++

#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <cstring>
using namespace std;
 
int n, m;
bool bisquares[250 * 250 * 2 + 1];
 
void setBisquares()
{
    for (int p = 0; p <= m; p++)
    {
        for (int q = 0; q <= m; q++)
            bisquares[p * p + q * q] = true;
    }
}
 
multimap<int,int> solve()
{
    multimap<int, int> ret;
    for (int a = 0; ; a++)
    {
        if (a + (n - 1) > 2 * pow(m, 2))
            break;
 
        for (int b = 1; ; b++)
        {
            if (a + (n - 1) * b  > 2 * pow(m, 2))
                break;
 
            bool ok = true;
            for (int seq = 0; seq < n; seq++)
            {
                int num = a + seq * b;
                if (bisquares[num] == false)
                {
                    ok = false;
                    break;
                }
            }
            if (ok)
                ret.insert(make_pair(b, a));
        }
    }
    return ret;
}
 
int main()
{
    ifstream fin("ariprog.in");
    ofstream fout("ariprog.out");
    
    fin >> n >> m;
 
    setBisquares();
    multimap<int, int> ret = solve();
 
    if (ret.empty())
        fout << "NONE" << endl;
    else
    {
        for (multimap<int, int>::iterator it = ret.begin(); it != ret.end(); it++)
            fout << it->second << " " << it->first << endl;
    }
 
    fin.close();
    fout.close();
    return 0;
}