Биквадратные арифметические прогрессии

[frankenstein]

Привет!
Название задачи некорректно, но интересно. А сама задача звучит так:
Даны целые числа $N \in [3, 25] $ и $M \in [1, 250]$
Дано множесто
$S = \{ x | x = p^2 + q^2 \}$
$ 0 \leqslant p, q \leqslant M $ p, q целые неотрицательные числа
Надо найти все $a, b$ такие, что
$\{ a, a+b, a+2b, ..., a+(N-1)b \} \in S$

Для решение я применил алгоритм поиска с возвратом.
Но перед началом, генерировал все биквадратные числа на нужном
отрезке и сохранял их в КЧ дерево.
Далее я попробовал перебрать все варианты в итоге получилось сложность алгоритма $O(n^2)$, где n это количество узлов дерева.
Алгоритм думаю легко будет читаться, даже если нет комментариев, так как там маленькие функции, и общий алгоритм
поиска с возвратом реализован отдельно. Вспомогательные алгоритмы переопределяются при наседовании класса.

Проблема в том, что при $N=25, M=250$, программа работает 35 секунд, а ограничение 5 сек. Не знаю какие
еще ветки отсечь.
Кажется, что при достаточно больших N, решений мало.

#define PROB_NAME "ariprog"

#include <algorithm>
#include <iostream>
#include <iterator>
#include <cassert>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
#include <list>
#include <map>

#define repeat(a) for (size_t i_ = 0; i_ < (a); ++i_)
#define whole(a) a.begin(), a.end()

template <class T>
class backtracker {
   private:
      /* TODO: how to give access to user for this variable */
      /* Used to stop backtracking */
      bool finished;

   protected:
      virtual bool solution_checker(std::vector<T> &, std::size_t) = 0;
      virtual void solution_handler(std::vector<T> &, std::size_t) = 0;
      virtual void candidate_setter(std::vector<T> &, std::size_t, std::vector<T> &) = 0;

   public:
      backtracker() : finished(false) {}

      /* Common algorithm of backtracking */
      void backtrack(std::vector<T> & a, size_t tos) {
         std::vector<T> c;

         if (solution_checker(a, tos)) {
            solution_handler(a, tos);
         } else {
            candidate_setter(a, tos, c);
            for (auto e: c) {
               a[tos] = e;
               backtrack(a, tos+1);
               if (finished) return;
            }
         }
      }
};

using namespace std;

class solution_t: public backtracker<int> {
   public:
      solution_t() {
         cin >> N >> M;
         generate_bisquare_set(M); // O(250^2)
      }

      void run() {
         vector<int> a(N);

         backtrack(a, 0); // O(very many)
         
         if (out.empty()) {
            cout << "NONE" << endl;
         } else {
            sort(whole(out)); // O(n log n)
            for (auto e: out)
               cout << e.second << ' ' << e.first << endl;
         }
      }

   protected:
      virtual void candidate_setter(vector<int> & a, size_t tos, vector<int> & c) {
         c.resize(0);
         switch (tos) {
            case 0: {
               for (auto e: bs_set)
                  c.push_back(e.first);
               break;
            }

            case 1: {
               /*for (auto e : bs_set) {
                  if (e.first > a[0] &&
                     a[0]+(e.first-a[0])*(N-1) <= bs_set.rbegin()->first)
                     c.push_back(e.first);
               }*/
               auto it = bs_set.find(a[0]);
               for (++it; it != bs_set.end(); ++it) {
                  if (a[0]+(it->first-a[0])*(N-1) <= bs_set.rbegin()->first)
                     c.push_back(it->first);
               }
            }
               /*
               for (int i = a[tos-1]+1; i <= bs_set.rbegin()->first; ++i)
                  if (bs_set.find(i) != bs_set.end())
                     c.push_back(i);
                     */
               break;

            default: {
               int n = a[tos-1]+a[1]-a[0];
               if (bs_set.find(n) != bs_set.end())
                  c.push_back(n);
               break;
            }
         }
      }

      virtual bool solution_checker(vector<int> & a, size_t tos) {
         return (tos == static_cast<size_t>(N));
      }

      virtual void solution_handler(vector<int> & a, size_t tos) {
         out.push_back(make_pair(a[1]-a[0], a[0]));
      }

      void generate_bisquare_set(int size) {
         for (int i = 0; i <= size; ++i)
            for (int j = 0; j <= size; ++j) {
               int n = i*i + j*j;
               bs_set.insert(make_pair(n, 1));
            }
      }

   private:
      int N, M;
      map<int, bool> bs_set;
      vector<pair<int, int> > out;
};

int main() {
   ifstream fin(PROB_NAME".in");
   ofstream fout(PROB_NAME".out");

   solution_t solution;
   solution.run();

   return 0;
}

[frankenstein]

Задача решилась!
std::vector достаточно медленна, получилось что проблема была в технологии с++, а не из-за алгоритма.
Тогда получается эта задача не в том разделе

[Toucan]

Тема перемещена из форума «Олимпиадные задачи (CS)» в форум «Программирование»