Запишем все решения для a ^ 3 + b ^ 3 = c ^ 3 + d ^ 3

Ответ 1

Используя хэш-карту для хранения (cube,(a,b)), вы можете перебирать все возможные пары целых чисел и вывести решение, как только обнаружите, что требуемая сумма кубов уже находится на карте.

псевдо-код:

map <- empty hash_map<int,list<pair<int,int>>>
for each a in range(0,10^5):
  for each b in range(a,10^5): //making sure each pair repeats only once
     cube <- a^3 + b^3
     if map.containsKey(cube):
         for each element e in map.get(cube):
            output e.first(), e.last(), a, b //one solution            
     else:
         map.put(cube,new list<pair<int,int>>)
     //for both cases, add the just found pair to the relevant list
     map.get(cube).add(cube,new pair(a,b))  

Это решение представляет собой O (n ^ 2) пространство ⁽¹⁾ и O (n ^ 2 + OUTPUT) в среднем, где OUTPUT - это размер вывода.

EDIT:

Требуемое пространство на самом деле O(n^2 logn), где n - диапазон (10 ^ 5), потому что для представления целых чисел 10^5 вам нужны бит ceil(log_2(10^15)) = 50. Итак, вам действительно нужно что-то вроде 500 000 000 000 бит (+ накладные расходы для карты и списка), что составляет ~ 58,2 ГБ (+ накладные расходы).

Так как для большинства машин это слишком много - вы можете захотеть сохранить данные на диске или, если у вас есть 64-битная машина, просто сохраните в "память" и пусть ОС и виртуальная память делает это как можно лучше.

(1) По мере того, как редактирование поясняется, это фактически пространство O(n^2log(n)), однако если мы берем каждое целочисленное хранилище как O(1) (как правило, это так), мы получаем пробел O(n^2). Тот же принцип будет применяться для временной сложности, очевидно.

Ответ 2

Использование очереди приоритетов - почти наверняка самое простое решение, а также наиболее практичное, так как это O (n) хранилище (с лог-фактором, если вам нужны бонусы). Любое решение, которое включает в себя вычисление всех возможных сумм и помещение их на карту, потребует хранения O (n ^ 2), что вскоре становится нецелесообразным.

Моя наивная, не оптимизированная реализация с использованием очереди приоритетов - это время O (n ^ 2 log (n)). Тем не менее, для n = 10000 и около 750 секунд для n = 100000 потребовалось меньше пяти секунд, используя пару мегабайт памяти. Это, безусловно, может быть улучшено.

Основная идея, согласно вашему комментарию, состоит в том, чтобы инициализировать очередь приоритета парами (a, a + 1) для a в диапазоне [1, N), а затем многократно увеличивать второе значение наименьшего (на сумма кубов) кортеж, пока не достигнет N. Если в любой момент наименьшие два элемента в очереди равны, у вас есть решение. (Я мог бы вставить код, но вы только попросили намек.)

Ответ 3

Более быстрое, чем тривиальное решение: вы вычисляете все значения, которые может иметь a ^ 3 + b ^ 3, и сохраняйте все возможные значения a и b с ним. Это делается путем циклического перехода через a и b, сохраняя результаты (a ^ 3 + b ^ 3) в двоичном дереве и имея список значений (a и b), связанных с каждым результатом.

После этого шага вам нужно пройти по списку и для каждого значения, выбрать все возможные назначения для a, b, c, d.

Я думаю, что это решение занимает время O (n ^ 2 log n) и O (n ^ 2), но я мог бы что-то пропустить.

Ответ 4

int Search(){
int MAX = 10000000;
for(int a = 0; a < MAX; a++){
    int a3 = a * a * a;
    if(a3 > MAX) break;
    for(int b = a; b < MAX; b ++){
        int b3 = b * b * b;
        if(a3 + b3 > MAX)break;             
        for(int c = 0; c < a; c++){
            int c3 = c*c*c;
            int m = a3 - c3; 
            int d = b+1;
            while(true){
                int d3 = d * d * d;
                if(d3-b3 <= m){
                    if((d3 - b3) == m){
                        count++;
                        PUSH_Modified(a3, b3, c3, b3, a, b, c, d);
                    }
                    d++;
                    continue;
                }
                else
                    break;
            }
        }
    }
}
return 0;

}

Ответ 5

Использование решения Hashmap (O (n ^ 2)):

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

import static java.lang.Math.pow;

/**
 * Created by Anup on 10-10-2016.
 */

class Pair {
    int a;
    int b;

    Pair(int x, int y) {
        a = x;
        b = y;
    }
}

public class FindCubePair {
    public static void main(String[] args) {
        HashMap<Long, ArrayList<Pair>> hashMap = new HashMap<>();
        int n = 100000;

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                long sum = (long) (pow(i, 3) + pow(j, 3));

                if(hashMap.containsKey(sum)) {
                    List<Pair> list = hashMap.get(sum);
                    for(Pair p : list) {
                        System.out.println(i + " " + j + " " + p.a + " " + p.b);
                    }
                } else {
                    ArrayList<Pair> list = new ArrayList<>();
                    hashMap.put(sum, list);
                }

                hashMap.get(sum).add(new Pair(i, j));
            }
        }
    }
}

К сожалению, значение напечатанных целых чисел даже не достигает 1000 на моем компьютере из-за ограничения ресурсов.

Ответ 6

Предположим, что решение:

a=A, b=B, c=C, and d=D.

Для любого решения мы можем сгенерировать еще 3 решения

abcd
ABCD

ABDC
BACD
BADC

Собственно, если A=B или C=D, тогда у нас может быть только 1 или 2 дополнительных решения.

Мы можем выбрать решения, которые мы ищем сначала, упорядочивая A <= B и C <= D. Это уменьшит пространство поиска. Мы можем генерировать пропущенные решения из найденных.

Всегда найдется хотя бы одно решение, где A=C и B=D. Мы ищем, когда A>C и B<D. Это происходит из упорядочения: C не может быть больше A, потому что, поскольку мы решили посмотреть только на решения, где D>C, сумма куба была бы слишком большой.

Мы можем вычислить A^3 + B^3, поместить его в map в качестве ключа, а vector из пар A,B в качестве значения.

Будут (n^2)/2 значения.

Если в A, и они будут теми решениями, которые мы ищем. Мы можем выводить их немедленно, вместе с их перестановками.

Я не уверен в сложности.

Ответ 7

Одно решение - использование понятия нахождения 2 суммы в отсортированном массиве. Это O (n3)

public static void pairSum() {
    int SZ = 100;
    long[] powArray = new long[SZ];
    for(int i = 0; i< SZ; i++){
        int v = i+1;
        powArray[i] = v*v*v;
    }
    int countPairs = 0;
    int N1 = 0, N2 = SZ-1, N3, N4;
    while(N2 > 0) {
        N1=0;
        while(N2-N1 > 2) {
            long ts = powArray[N1] + powArray[N2];
            N3 = N1+1; N4 = N2-1;
            while(N4 > N3) {
                if(powArray[N4]+powArray[N3] < ts) {
                    N3++;
                }else if(powArray[N4]+powArray[N3] > ts) {
                    N4--;
                }else{
                    //System.out.println((N1+1)+" "+(N2+1)+" "+(N3+1)+" "+(N4+1)+" CUBE "+ts);
                    countPairs++;
                    break;
                }
            }
            N1++;
        }
        N2--;
    }
    System.out.println("quadruplet pair count:"+countPairs);
}

Ответ 8

Начиная с подхода грубой силы, его довольно очевидно, что будет выполнено время O (n ^ 4). Если пространство не является ограничением, мы можем пойти на комбинацию списка и карт. Код не требует пояснений, мы используем вложенный список для отслеживания всех записей для конкретной суммы (ключ на карте). Таким образом, временная сложность уменьшается от O (n ^ 4) до O (n ^ 2)

public void printAllCubes() {
  int n = 50;
  Map<Integer, ArrayList<ArrayList>> resMap = new HashMap<Integer, ArrayList<ArrayList>>();
  ArrayList pairs = new ArrayList<Integer>();
  ArrayList allPairsList = new ArrayList<ArrayList>();
  for (int c = 1; c < n; c++) {
    for (int d = 1; d < n; d++) {
      int res = (int) (Math.pow(c, 3) + Math.pow(d, 3));
      pairs.add(c);
      pairs.add(d);
      if (resMap.get(res) == null) {
        allPairsList = new ArrayList<ArrayList>();
      } else {
        allPairsList = resMap.get(res);
      }
      allPairsList.add(pairs);
      resMap.put(res, allPairsList);
      pairs = new ArrayList<Integer>();
    }
  }

  for (int a = 1; a < n; a++) {
    for (int b = 1; b < n; b++) {
      int result = (int) (Math.pow(a, 3) + Math.pow(b, 3));
      ArrayList<ArrayList> pairList = resMap.get(result);
      for (List p : pairList) {
        System.out.print(a + " " + b + " ");
        for (Object num : p)
          System.out.print(num + " ");
        System.out.println();
      }
    }
  }
}

Ответ 9

Логика:
a ^ 3 + b ^ 3 = c ^ 3 + d ^ 3
Тогда a ^ 3 + b ^ 3-c * 3-d ^ 3 = 0
Попробуйте решить это уравнение, поставив все комбинации значений для a, b, c и d в диапазоне от [0, 10 ^ 5].
Если уравнение решено, напечатайте значения a, b, c и d

public static void main(String[] args) {

        //find all solutions of a^3 + b^3 = c^3 + d^3
        double power = 3; 
        long counter = 0; // to count the number of solution sets obtained
        int limit = 100000; // range from 0 to limit

        //looping through every combination of a,b,c and d
        for(int a = 0;a<=limit;a++)
        {
            for(int b = 0;b<=limit;b++)
            {
                for(int c = 0;c<=limit;c++)
                {
                    for(int d = 0;d<=limit;d++)
                    {
                        // logic used : a^3 + b^3 = c^3 + d^3 can be written as a^3 + b^3 - c^3 - d^3 = 0
                        long result = (long)(Math.pow(a,power ) + Math.pow(b,power ) - Math.pow(c,power ) - Math.pow(d,power ));
                        if(result == 0 )
                        { 
                            counter++; // to count the number of solutions
                            //printing the solution
                            System.out.println( "a = "+ a + "    b = " + b + "    c = " + c + "    d = " + d);
                        }
                    }
                }
            }
        }
        //just to understand the change in number of solutions as limit and power changes

        System.out.println("Number of Solutions =" + counter);
    }