Лучший алгоритм для нахождения максимального числа, на которое квадрат делит K :

Я уверен, что кто-то еще придумает хороший ответ, связанный с арифметикой модуля. Вот наивный подход...

Каждый из факторов может быть сам по себе факторизован (хотя это может быть дорогостоящей операцией).

Учитывая факторы, вы можете искать группы повторяющихся факторов.

Например, используя ваш пример:

Простые множители 9: 3, 3

Простые множители 6: 2, 3

Все простые множители: 2, 3, 3, 3

Есть две тройки, поэтому у вас есть ответ (квадрат 3 делит 54).

Второй пример 36 х 9 = 324

Простые множители числа 36: 2, 2, 3, 3

Простые множители 9: 3, 3

Все простые множители: 2, 2, 3, 3, 3, 3

Итак, у вас есть две двойки и четыре тройки, что означает повторение 2x3x3. 2x3x3 = 18, значит, квадрат 18 делит 324.

Изменить: прототип Python

import math

def factors(num, dict):
    """ This finds the factors of a number recursively.
        It is not the most efficient algorithm, and I 
        have not tested it a lot.  You should probably
        use another one. dict is a dictionary which looks
        like {factor: occurrences, factor: occurrences, ...}
        It must contain at least {2: 0} but need not have 
        any other pre-populated elements.  Factors will be added
        to this dictionary as they are found.
    """

    while (num % 2 == 0):
        num /= 2
        dict[2] += 1
    i = 3
    found = False
    while (not found and (i <= int(math.sqrt(num)))):
        if (num % i == 0):
            found = True
            factors(i, dict)
            factors(num / i, dict)
        else:
            i += 2
    if (not found):
        if (num in dict.keys()):
            dict[num] += 1
        else:
            dict[num] = 1
    return 0


#MAIN ROUTINE IS HERE

n1 = 37 # first number (6 in your example)
n2 = 41 # second number (9 in your example)
dict = {2: 0} # initialise factors (start with "no factors of 2")
factors(n1, dict) # find the factors of f1 and add them to the list
factors(n2, dict) # find the factors of f2 and add them to the list
sqfac = 1
# now find all factors repeated twice and multiply them together
for k in dict.keys():
    dict[k] /= 2
    sqfac *= k ** dict[k]
# here is the result
print(sqfac)

Ответ на C++

int func(int i, j)
{ 
    int k = 54
    float result = pow(i, 2)/k
    if (static_cast<int>(result)) == result) 
    {
        if(i < j)
        {
            func(j, i);
        }
        else
        {
            cout << "Number is correct: " << i << endl;
        }
    }
    else
    {
        cout << "Number is wrong" << endl;
        func(j, i)

    }
 }

Пояснение:

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

Если я правильно понял проблему, я вижу, что у вас есть прямоугольник длины = A, ширины = B и площади = K, и вы хотите преобразовать его в квадрат и потерять минимально возможную площадь.

Если это так. Таким образом, проблема с вашим алгоритмом заключается не в стоимости повторения нескольких итераций до получения результата. Скорее проблема в том, что ваш алгоритм сильно зависит от длины A и ширины B входного прямоугольника. В то время как она должна зависеть только от площади K

Например:

• Предположим, что А = 1, В = 25.
• Тогда K=25 (прямоугольная область)
• Ваш алгоритм возьмет минимальное значение, равное A, и примет его как ответ с одной итерацией, которая настолько быстра, но приводит к неправильному ответу, поскольку в результате получается квадрат площади 1 и тратятся оставшиеся 24 (независимо от того, см или м)
• В то время как правильный ответ здесь должен быть 5. который никогда не будет достигнут вашим алгоритмом

Итак, в моем решении я предполагаю один вход K

Мои идеи заключаются в следующем

• х = квадрат (К)
• if(x is int) .. x это ответ
• иначе цикл от x-1 до 1, x--
• если K/x^2 равно int, x является ответом

Это может потребовать дополнительных итераций, но гарантирует точный ответ. Кроме того, могут быть некоторые опасения по поводу стоимости sqrt (K), но он будет вызываться только один раз, чтобы избежать вводящих в заблуждение значений длины и ширины.