Двойные квадраты: считая числа, которые являются суммами двух идеальных квадратов

Question

Источник: Facebook Hacker Cup Отборочный раунд 2011

Число с двойным квадратом - это целое число X, которое можно выразить как сумму двух идеальных квадратов. Например, 10 - это двойной квадрат, потому что 10 = 3 ² + 1 ² . Учитывая X, как мы можем определить количество способов, которыми оно может быть записано как сумма двух квадратов? Например, 10 можно записать только как 3 ² + 1 ² (мы не считаем 1 ² + 3 ² как быть другим). С другой стороны, 25 можно записать как 5 ² + 0 ² или как 4 ² + 3 ² .

Вам нужно решить эту проблему за 0 ≤ X ≤ 2 147 483 647.

Примеры:

• 10 => 1
• 25 => 2
• 3 => 0
• 0 => 1
• 1 => 1

Answer 1

Факторизуйте число n и проверьте, есть ли у него простой множитель p с нечетной оценкой, такой что p = 3 (mod 4). Это происходит тогда и только тогда, когда n не является суммой двух квадратов.

Число решений имеет выражение в замкнутой форме, включающее число делителей n. См. это, теорема 3 для точного утверждения.

Answer 2

Вот мой простой ответ: O(sqrt(n)) сложность

x^2 + y^2 = n
x^2 = n-y^2 
x = sqrt(n - y^2)

x должно быть целым числом, поэтому (n-y^2) должно быть идеальным квадратом.Перейдите к y=[0, sqrt(n)] и проверьте, является ли (n-y^2) идеальным квадратом или нет

Псевдокод :

count = 0;
for y in range(0, sqrt(n))
    if( isPerfectSquare(n - y^2))
         count++
return count/2

Answer 3

Вот гораздо более простое решение:

create list of squares in the given range (that's 46340 values for the example given)

for each square value x
  if list contains a value y such that x + y = target value (i.e. does [target - x] exist in list)
    output √x, √y as solution (roots can be stored in a std::map lookup created in the first step)

Answer 4

Вот версия, которая тривиально O (sqrt (N)) и избегает всех внутренних контуров цикла.

Начните с генерации всех квадратов до предела, легко сделанных без каких-либо умножений, затем инициализируйте al иr index.

На каждой итерации вы вычисляете сумму, затем обновляете два индекса и счет на основе сравнения с целевым значением.Это sqrt (N) итераций для генерации таблицы и максимальные sqrt (N) итераций цикла поиска.Расчетное время работы с приемлемым компилятором составляет максимум 10 тактов на квадрат (N), поэтому для максимального входного значения, если 2 ^ 31 (sqrt (N) ~ = 46341), это должно соответствовать менее 500K тактов или нескольким десятымсекунды:

unsigned countPairs(unsigned n)
{
    unsigned sq = 0, i;
    unsigned square[65536];

    for (i = 0; sq <= n; i++) {
        square[i] = sq;
        sq += i+i+1;
    }

    unsigned l = 0, r = i-1, count = 0;

    do {
        unsigned sum = square[l] + square[r];
        l += sum <= n;       // Increment l if the sum is <= N
        count += sum == n;   // Increment the count if a match
        r -= sum >= n;       // Decrement r if the sum is >= N
    } while (l <= r);
    return count;
}

Хороший компилятор может заметить, что все три сравнения в конце используют одни и те же операнды, поэтому ему нужен только один код операции CMP, за которым следуют три различные операции условного перемещения (CMOVcc).

Answer 5

Цикл по всем парам (a, b) невозможен, учитывая ограничения на X. Однако есть более быстрый путь!

Для фиксированного a мы можем отработать b: b = √ (X - a ² ). b не всегда будет целым числом, поэтому мы должны это проверить. Из-за проблем с точностью выполните проверку с небольшим допуском: если b равно x.99999, мы можем быть уверены, что это целое число. Таким образом, мы перебираем все возможные значения a и подсчитываем все случаи, когда b является целым числом. Мы должны быть осторожны, чтобы не считать дважды, поэтому мы устанавливаем ограничение, что a <= b. Для X = a <sup>2 + b ² a будет не более √ (X / 2) с этим ограничением.

Вот реализация этого алгоритма в C ++:

int count = 0;
// add EPS to avoid flooring x.99999 to x
for (int a = 0; a <= sqrt(X/2) + EPS; a++) {
    int b2 = X - a*a; // b^2
    int b = (int) (sqrt(b2) + EPS);
    if (abs(b - sqrt(b2)) < EPS) // check b is an integer
        count++;
}
cout << count << endl;

См. На ideone с вводом образца

Answer 6

Число решений (x, y)

x ^ 2 + y ^ 2 = n

над целыми числами ровно в 4 раза больше числа делителей n, равного 1мод 4. Аналогичные тождества существуют и для задач

x ^ 2 + 2y ^ 2 = n

и

x ^ 2 + y ^ 2 + z ^ 2 +w ^ 2 = n.

Answer 7

Я торопился, поэтому решил его, используя довольно грубый подход (очень похожий на подход marcog) с использованием Python 2.6.

def is_perfect_square(x):
    rt = int(math.sqrt(x))
    return rt*rt == x

def double_sqaures(n):
    rng = int(math.sqrt(n))
    ways = 0
    for i in xrange(rng+1):
        if is_perfect_square(n - i*i):
            ways +=1
    if ways % 2 == 0:
        ways = ways // 2
    else:
        ways = ways // 2 + 1
    return ways

Примечание: ways будет нечетным, когда числоидеальный квадрат.