0 / 0 / 0
Регистрация: 01.05.2019
Сообщений: 7
|
||||||
1 | ||||||
Найдите такое минимальное натуральное n, что Bn делится на A03.05.2019, 09:44. Показов 15492. Ответов 41
Метки нет (Все метки)
Помогите, пожалуйста!
Даны два натуральных числа A и B (2 A, B 2 * 109). Найдите такое минимальное натуральное n, что Bn делится на A. Входные данные Программа получает на вход два числа A и B. Выходные данные Программа выводит одно значение n. Если никакая степень числа B не делится на A, то выведите число -1. Вот рабочий код, но он не проходит один единственный тест
0
|
03.05.2019, 09:44 | |
Ответы с готовыми решениями:
41
Для заданного натурального А найти минимальное натуральное N такое, что N в степени N делится на A Найти минимальное натуральное N такое, что N в степени N делится на A Найти такое минимальное натуральное n, что B^n делится на A Найти минимальное натуральное N такое, что N в степени N делится на A |
0 / 0 / 0
Регистрация: 04.05.2019
Сообщений: 1
|
||||||
05.05.2019, 22:25 | 3 | |||||
Зачем так много проверок? Хватает просто
0
|
0 / 0 / 0
Регистрация: 13.05.2019
Сообщений: 1
|
|
13.05.2019, 22:47 | 4 |
проверь делятся ли числа в начале
0
|
8 / 12 / 2
Регистрация: 08.08.2019
Сообщений: 63
|
||||||
12.08.2019, 11:08 | 5 | |||||
Очень некрасивый, нерациональный код. Используйте только в крайнем случае
0
|
Заблокирован
|
||||||
02.08.2020, 10:29 | 6 | |||||
Зачем так много? Зачем столько функций? Всё проще:
найти такое , что Если существует такое , что , то ответ -1, так как никогда в разложении не будет . В противном случае - если ответ - m, то для любого - минимальная степень, чтобы был возможен ответ. Добавлено через 2 минуты И еще: странно, что у Вас работает функция quit()
0
|
8196 / 4321 / 1832
Регистрация: 27.03.2020
Сообщений: 7,146
|
||||||
02.08.2020, 10:50 | 7 | |||||
Затем берется максимальное отношение степени множителя в "А" к аналогичному в "В"
2
|
0 / 0 / 0
Регистрация: 29.07.2020
Сообщений: 31
|
|
03.08.2020, 22:20 | 8 |
Gdez, Здравствуйте! Можете пожалуйста разъяснить принцип своего решения (можно относительно теории чисел, я тоже из Сириуса ). Я вас еще спрашивал про задачу о романе в томах (огромное спасибо за объяснение, сам решил все остальные задачи про бин поиск благодаря вам). Мой главный вопрос: каким образом "взятие максимального (почему не минимального, просят же найти минимальное n) отношения степени множителя в А к аналогичному в В" гарантирует нам, что это будет правильным ответом (а не будет например больше или меньше нужного B^n, а также будет делиться на А, ведь изначально B может не делиться на A)? Как я понял, вы находите это пресловутое максимальное отношение и возводите в него все простые множители разложения числа B. Например есть числа A: 24 = 2^3 * 3^1 и B: 36 = 2^2 * 3^2. Далее максимальное отношение степеней равно [3/2] = 2. Таким образом у нас получается: B^n = (2^2 * 3^2)^2 = 36^2 = 576, которое делится и на 36, и на 24.
0
|
8196 / 4321 / 1832
Регистрация: 27.03.2020
Сообщений: 7,146
|
|
03.08.2020, 22:49 | 9 |
Здравствуйте
Ну здесь просто - значения степеней простых множителей в числе А должно быть меньше или равно значениям степеней таких же множителей в числе В. Если р1 = 7, р2 = 5, р3 = 4 (значение степеней простых множителей) в числе А, а в числе В - р1 = 2, р2 = 1, р3 = 7, р4 = 2. Значит для для В^n р1>=7 (увеличить в 3,5 раза) р2>= 5 (в 5 раз), р3 >=4 (уже больше), р4 - значения не имеет (его нет в А). Так как увеличить степень отдельным множителям не можем, то увеличиваем на максимум - в 5 раз и получим для В^n - p1=10, p2=5, p3=35, p4= 10. При В^n/A получим: (р1^10 * р2^5 * р3^35 * р4^10) / (р1^7 * р2^5 * р3^4) = р1^(10-7) * р2^(5-5) * р3^(35-4) * р4^10 = р1^3 * р2^0 * р3^31 * р4^10 У множителя р2 степень минимальна и равна "0". Остальные не отрицательны. Если мы взяли n = 4, то получили бы р2^(-1), то есть = р1^1 * р3^24 * р4^8 / р2^(-1) Так как р1, р2 и тд простые множители, то последнее решение не было бы целым числом. Напомню, "n" для р1 предполагалось 3.5, для р2 - 5, для р3 ~ 0.57, для р4 - 0 Поэтому нужно находить "максимальное" отношение показателей степени у соответствующих множителей для получения "минимального" n.
0
|
0 / 0 / 0
Регистрация: 29.07.2020
Сообщений: 31
|
|||||||||||
04.08.2020, 10:29 | 10 | ||||||||||
Gdez, Спасибо, что объяснили. Я решил задачу. Всё бы хорошо, но из за некоторых различий между С++ и Питоном (Я пишу код на С++) мне пришлось добавить в код еще несколько конструкций и если честно я не понимаю почему мой код работает. Вот мой код, покажу что изменил (ПРОГРАММА ОЧЕНЬ ПОХОЖА НА ВАШУ):
Добавлено через 11 минут Gdez, Добавил комментарии в код
0
|
8196 / 4321 / 1832
Регистрация: 27.03.2020
Сообщений: 7,146
|
|
04.08.2020, 12:41 | 11 |
По условию n <= 2*10^9
Т.е. в тестах нет больше этого числа -(-pa[key]//pb[key]) - округление вверх - 3/2 = 2 , 2/2 = 1 Добавлено через 8 минут Количество множителей у чисел больше 30 на порядок меньше самого числа - у 30 три множителя
0
|
0 / 0 / 0
Регистрация: 29.07.2020
Сообщений: 31
|
|
04.08.2020, 16:37 | 12 |
Gdez, Да, я понимаю. Проблема в том, что из-за индивидуальных особенностей C++ я не могу создать массив размером больше, чем несколько миллионов (точную цифру не знаю). Представьте, что n - простое число и на числовой прямой находится рядом с числом 2*10^9. Тогда, в функции factorization после окончания цикла while d * d <= n, n останется самим собой (ни один раз n не разделится на d). В этом случае придётся выполнить операцию p[n] += 1, но тогда произойдёт выход за границы массива, а увеличить его вместимость я не могу. Поэтому приходится прибегать к использованию каких-то костылей, таких как условие if (fora[0] == -1 || forb[0] == - 1), работу которого Я НЕ МОГУ ПОНЯТЬ (Это мой главный вопрос, выделю капсом), хоть я сам и написал это условие. А именно я не могу понять работу условия if (b % a != 0 && forb[1] % a == 0). Ещё вопрос: Если после окончания цикла while d * d <= n, n все еще больше 1, могу ли я утверждать, что оставшееся от деления на d n является простым числом? (Например: n = 14 -> d = 2 -> n = 14 : 2 = 7 -> n = 7), при условии, что ЦИКЛ ПРОВЕРИТ ВСЕ d в диапазоне [2;2000000]. Если я так могу утверждать, то получается, что условие forb[1] % a == 0 я могу заменить на forb[1] == a так как forb[1] = n (n которое не до конца разделилось), а также так как n является простым числом (если моя гипотеза об утверждении, что неразделившееся n - простое число верна). Соответственно у такого простого n может быть только один делитель равный a, так как, я повторюсь, это n является простым числом. Но дело в том, что если я заменю изначальное условие на forb[1] == a, то один тест не будет проходить. Я в замешательстве: моя гипотеза одновременно логически верна, но на практике не работает. Меня в принципе не устраивает forb[1] % a == 0 (Это условие изначально написано в коде). Меня бы скорей устроило forb[1] % a != 0 (не равно) потому, что по логике A и B должны иметь одинаковый набор простых множителей, и если n не делится на А, то тогда нужно сразу выводить -1, но по какой-то причине нужно действовать по другому. Как это объяснить с точки зрения математики?
0
|
8196 / 4321 / 1832
Регистрация: 27.03.2020
Сообщений: 7,146
|
|
04.08.2020, 17:10 | 13 |
А почему у тебя n <= 2000000 ?
Добавлено через 35 секунд По условию 2000000 000 или 2000000000 Добавлено через 7 минут Подпрограмма прогоняет числа до корня квадратного от исходного. От этого значения до числа n множителей больше математически не может быть, кроме самого числа Т.е. forb лежит в диапазоне [2 : \sqrt{n}] плюс еще само n Добавлено через 3 минуты И еще - в коде не нашел проверки : есть ли очередное значение fora в списке forb
0
|
0 / 0 / 0
Регистрация: 29.07.2020
Сообщений: 31
|
|
04.08.2020, 17:10 | 14 |
Gdez, Как я понимаю, элементы массива P являются степенями, а их индексы - их множителями. Например если P[2] = 2 -> 2^2. Теперь представьте наихудшую ситуацию, когда n максимально приближенно к 2 * 10^9 И ЯВЛЯЕТСЯ ПРОСТЫМ ЧИСЛОМ. Таким образом, после окончания цикла в функции n останется самим собой (n > 1). И тогда мне придётся выполнять операцию P[n] += 1. Но я на могу обратиться к такому большому индексу, так как максимальная вместимость массива - всего несколько миллионов. Если попытаетесь ещё расширить массив, то программа выдаст ошибку. Таким образом, с n, большим чем 2000000 (Это число я выбрал сам, так как по-моему мнению оно гарантирует перебор всех возможных d или другими словами в худшем случае d может равняться 2 000 000). Поэтому с «трудными» n, которые не смогли разделиться, даже пройдя через цикл while, приходиться работать ИНДИВИДУАЛЬНО.
0
|
8196 / 4321 / 1832
Регистрация: 27.03.2020
Сообщений: 7,146
|
|
04.08.2020, 17:13 | 15 |
Кажется понял
У меня P - словарь, где ключ - это множитель, а значение ключа - степень этого множителя
0
|
0 / 0 / 0
Регистрация: 29.07.2020
Сообщений: 31
|
|
04.08.2020, 17:13 | 16 |
Gdez, первый if в цикле for проверяет НЕ встречается ли элемент А в Б. Если не встречается, то выводит -1, иначе - идёт дальше.
0
|
8196 / 4321 / 1832
Регистрация: 27.03.2020
Сообщений: 7,146
|
|
04.08.2020, 17:13 | 17 |
В С++ словари же тоже есть?
0
|
0 / 0 / 0
Регистрация: 29.07.2020
Сообщений: 31
|
|
04.08.2020, 17:18 | 18 |
Gdez, Да, вы все правильно поняли
Добавлено через 1 минуту Gdez, да, есть. Но кстати тут я не использую словарь, просто массив, где его элемент - степень, а индекс - множитель Добавлено через 2 минуты Gdez, Кстати, проверка fora[i] == forb [i] абсолютно не нужна (в цикле for). Достаточно и моей реализации подсчета переменной k, как у вас в коде, у меня это x
0
|
8196 / 4321 / 1832
Регистрация: 27.03.2020
Сообщений: 7,146
|
|
04.08.2020, 17:22 | 19 |
Если не ошибаюсь, индексы идут непрерывно по натуральным числам.
Тогда Р очень большая Например для n = 36 будет р[0] = 0, р[1] = 0, р[[2] = 2, р[3] = 2, р[4] = 0 ...... р[36]=0 Так?
0
|
0 / 0 / 0
Регистрация: 29.07.2020
Сообщений: 31
|
|
04.08.2020, 17:23 | 20 |
Gdez, Все верно. Если попросить вывести P после окончания цикла, то будет очень много нулей
0
|
04.08.2020, 17:23 | |
04.08.2020, 17:23 | |
Помогаю со студенческими работами здесь
20
Найти минимальное натуральное N такое, что N в степени N делится на A Найти минимальное натуральное N такое, что N в степени N делится на A Найти минимальное натуральное N такое, что N в степени N делится на A Найти минимальное натуральное N такое, что N в степени N делится на A Найдите наименьшее натуральное n такое, что 2^n + 5^n − n делится на 1000 Найти минимальное натуральное N такое, что N в степени N делится на заданное число Для заданного натурального A найти минимальное натуральное N такое, что N в степени N делится на A Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |