Как найти все квадраты в числе (Java)?

Question

Кажется, у меня психическое расстройство, и я не могу решить следующую проблему.По сути, я хочу найти все возможные квадраты в данном числе, то есть N = S * S * A, где N в данном числе, S * S - это квадрат, а A - это какое-то другое число.И мне нужно найти все возможные комбинации такого рода.
До сих пор я разложил число N в последовательности простых чисел и построил карту, где ключи - это уникальные простые числа в последовательности, а значения - это числовхождения этого простого числа.
Например, для некоторого числа может быть такая последовательность:
2 2 2 3 3 5 5 5 5 7 7 7 7 7,
таким образом, квадраты должны быть 4,9, 25, 49, 36, 100, 196, 225, 441, 1225. Для такой последовательности у меня будет следующая карта:
2 3
3 2
5 4
7 5
Далее я уменьшаю нечетные значения на единицу:
2 2
3 2
5 4
7 4
Главный вопрос - как получить квадраты, написанные выше, с этой карты.Моя идея состояла в том, чтобы запустить 2 цикла (не знаю, насколько это эффективно):

for(Map.Entry<BigInteger, Integer> entry : frequency.entrySet()) {
    for(Map.Entry<BigInteger, Integer> ientry : frequency.entrySet()) {
    }
}

Очевидно, как умножить все пары ключей на карте, но я не могу придумать условия, которые мне нужно навязатьпринять во внимание кратности.
Заранее большое спасибо!
Ps Есть ли хороший способ без вложенных циклов?

Answer 1

Я не думаю, что здесь вам помогут вложенные циклы; Вы входите на территорию рекурсии. : -)

Проблема, которую вы задаете, сводится к этому. У вас есть список номеров, а также частоты этих номеров. Вы хотите придумать все уникальные способы, которыми вы можете выбрать некоторое количество копий каждого номера. Например, учитывая

2 2
3 4
5 2

Вы бы хотели

2 ⁰ 3 ⁰ 5 ⁰

2 ⁰ 3 ⁰ 5 ²

2 ⁰ 3 ² 5 ⁰

2 ⁰ 3 ² 5 ²

2 ⁰ 3 ⁴ 5 ⁰

2 ⁰ 3 ⁴ 5 ²

2 ² 3 ⁰ 5 ⁰

2 ² 3 ⁰ 5 ²

2 ² 3 ² 5 ⁰

2 ² 3 ² 5 ²

2 ² 3 ⁴ 5 ⁰

2 ² 3 ⁴ 5 ²

Если мы просто напишем показатели, то у нас будет

0 0 0
0 0 2
0 2 0
0 2 2
0 4 0
0 4 2
2 0 0
2 0 2
2 2 0
2 2 2
2 4 0
2 4 2

Итак, вопрос в том, как вы можете создать это. К счастью, есть действительно красивая рекурсивная формулировка для генерации этих чисел. Это выглядит примерно так. Мы хотим написать функцию AllSquares, которая принимает список пар простых чисел и их кратностей, а затем возвращает все возможные произведения, которые можно сформировать из тех простых чисел, которые являются идеальными квадратами. Мы сделаем это индуктивно.

В нашем базовом случае, если вы предоставляете пустой список для AllSquares, то существует ровно один квадратный продукт, то есть 1, пустой продукт элементов пустого списка.

Для индуктивного шага предположим, что у нас есть непустой список, первый элемент которого (простое число, кратность), а остальные элементы - «покой». Предположим, что мы рекурсивно вычисляем список «комбинаций», сформированный путем вызова AllSquares для остальных элементов списка. Тогда для i = 0, 2, 4, ..., кратности, если вы возьмете элементы в списке и умножите их на основание ⁱ , вы получите новый список идеальных квадратов. Если вы возьмете объединение всех этих значений, вы получите все возможные идеальные квадраты, которые вы можете сформировать из чисел. Самое интересное в том, что это работает, даже если кратности нечетны, поскольку вы будете рассматривать только четные экспоненты.

Вот простой Java-код, который реализует этот алгоритм. Это совсем не эффективно, но оно имеет смысл:

private static List<Integer> allSquares(List<BaseMultiplicity> elems) {
    /* Base case: If the list is empty, there's only one square. */
    if (elems.isEmpty()) {
        return Collections.singletonList(1);
    }

    /* Recursive case: Compute the answer for the rest of the list. */
    List<BaseMultiplicity> rest = new LinkedList<BaseMultiplicity>(elems);
    rest.remove(0);
    List<Integer> recResult = allSquares(rest);

    /* Now, for each even power of this number, add appropriately-scaled
     * copies of the recursive solution to the result.
     */
    List<Integer> result = new ArrayList<Integer>();
    for (int i = 0, base = 1; i < elems.get(0).multiplicity; 
         i += 2, base *= elems.get(0).prime)
        for (Integer elem: recResult)
            result.add(elem * base * base);

    return result;
}

Надеюсь, это поможет!

Answer 2

Для N = S * S * A вычислите делители S и возведите их в квадрат.

Таким образом, учитывая вашу карту, вы можете вдвое уменьшить каждый показатель степени, это дает вам факторизацию S.

Затем вычислите числа, соответствующие всем комбинациям показателей, чтобы получить делители, как обычно.

Вот моя функция для этого:

public static NavigableSet<Long> divisors(long n)
{
    NavigableSet<Long> divisors = new TreeSet<Long>();
    divisors.add(1L);
    final Multiset<Long> factorization = primeFactorization(n);
    for (final long primeFactor : factorization.elementSet())
    {
        final int exponent = factorization.getMultiplicity(primeFactor);

        final NavigableSet<Long> newDivisors = new TreeSet<Long>(divisors);
        for (final long d : divisors)
        {
            for (int i = 0; i <= exponent; i++)
            {
                newDivisors.add(d * pow(primeFactor, i));
            }
        }
        divisors = newDivisors;
    }
    return divisors;
}

Multiset - это, в основном, карта от элементов до неотрицательных целых чисел.

Answer 3

Я бы решил эту проблему как комбинаторную задачу.

1. разложить и подсчитать простые множители.

2. построить список таким образом, чтобы, если коэффициент появился 2N или 2N + 1 раз в исходном числе, коэффициент появился в этом списке N раз. Таким образом, для простых факторов 2 2 2 2 2 3 3 5 список будет 2 2 3

3. построение списка всех комбинаций предыдущего списка; например {2} {2} {3} {2 2} {2 3} {2 3} {2 2 3}.

4. умножить коэффициенты в каждом наборе; например {2 2 3 4 6 6 12}.

5. исключить дубликаты, чтобы получить список значений S; например {2 3 4 6 12}.

Теперь переведите на Java.

(Построение списка всех комбинаций может быть выполнено итеративно или рекурсивно ... или путем создания и использования сторонней библиотеки. Кроме того, вы можете устранить дубликаты на шаге 3; т.е. создать set уникальных комбинаций.)