Problem 1.5.2 Arithmetic Progressions

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

 

 

문제 설명

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

TIME LIMIT: 5 secs

입력 

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.

출력

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.

입력 예

5 
7

출력 예

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

---

문제 풀이 내용

먼저, 제곱수들의 합들의 집합을 만든다. 이때, 집합의 값들을 같이 저장해두고, 검색할때 참고한다. 

검색하는 대상을 줄일 수 있는 방법을 찾는다. 일단,  a + b*n 이라고 수열을 정의한다. 

N개의 수열이 모두 집합에 있다고 하면,  a + b * (N-1) < 2 * M * M  이 된다. 여기에서 b의 범위를 축소하면,  b < 2*M*M/(N-1) 이 된다. 또, 제곱수들의 합인 집합에서 더하는 제곱수들이 커지면 집합내의 수들의 간격이 넓어진다.

3^2 + 4^2 = 25, 4^2+4^2 = 32  gap : 9 vs. 100^2 + 100^2 = 200, 100^2 + 101^2 = 221 gap: 21

그러므로, 만들어진 수  a + b * (N-1) 가 제곱수 합의 집합에 있는지 검사할 때는 큰 수들에서부터 검색하면 없는 경우를 더 빨리 찾을 수 있다.

프로그램 내용

#define MAX_N 25 /// 3 <= N <= 25
#define MAX_M 250 /// 1 <= M <= 250
#define MAX_SEQUENCE 10000

/// TIME LIMIT: 5 secs

int main() {
    int N=0; int M=0;
    fin >> N >> M;

    bool noneF = true;

    /// 0 <= p, q <= M

    /// build bisqueare sets
    bool bsqurares[2*M*M+1] = {false};
    int places[4*M*M] = {0};
    int pl=0;

    for (int idx1=0; idx1 < M+1 ; ++ idx1)
        for (int idx2 = 0; idx2< M+1 ; ++ idx2)
            if(!bsqurares[idx1*idx1 + idx2*idx2])
                bsqurares[idx1*idx1 + idx2*idx2] = true;
                places[pl] =  idx1*idx1 + idx2*idx2;
                pl++;

    /// find in bsquares
    /// a in bsquare, a+b in bsquare, ... a + (n-1)b in bsquare
    /// (N-1) * b <= 2*M*M => b <= 2*M*M/(N-1)
    /// a + b*(N-1) < 2*M*M ... backward search (N-1) ...0 
    /// many gap in bsquare for bigger numbers
 
    for (int def=1; def <= M*M*2/(N-1);def++) /// b
        for (int p = 0; places[p]<= (M*M*2 - ((N-1)*def)); p++) /// a
            bool is;
            is = true;
            int where;

            for (int c = (N-1); c>=0 ; c--)
                if (places[p]+c*def > 2*M*M) break;
                if (!bsqurares[places[p]+c*def]) /// a+ b*n
                    is = false;
                    where = (p+c*def);

 

Chapter 1. Getting started