Найдите такое минимальное натуральное n, что Bn делится на A

@airh4ck · Регистрация: 01.05.2019

Студворк — интернет-сервис помощи студентам

Помогите, пожалуйста!
Даны два натуральных числа A и B (2 A, B 2 * 109). Найдите такое минимальное натуральное n, что Bn делится на A.

Входные данные
Программа получает на вход два числа A и B.

Выходные данные
Программа выводит одно значение n. Если никакая степень числа B не делится на A, то выведите число -1.
Вот рабочий код, но он не проходит один единственный тест

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def gcd(a, b):
    while a != 0 and b != 0:
        if a > b:
            a = a % b
        else:
            b = b % a
    return a + b
a, b = int(input()), int(input())
if a == b == 1:
    print (1)
    quit()
elif (a % 2 == 0 and b % 2 != 0) or (a % 2 != 0 and b % 2 == 0) or gcd(a, b) == 1:
    print(-1)
    quit()
 
flag = False
for i in range(1, int(max(a, b) ** (1/2)) + 100):
    if pow(b, i, a) == 0:
        flag = True
        break
if flag:
    print(i)
else:
    print(-1)

Что я не предусмотрел???

@Senjey · 31.08.2020, 11:57

dfgdfghfhvhvh, "Ответ - 2" имелось ввиду просто 2.
21*21(441) кратно 9 !!!! Как раз это правильный ответ

@dfgdfghfhvhvh · 31.08.2020, 12:56

Gdez, вы неправильно понимаете алгоритм программы, которая написана мной выше. cicadacand - число, на которое может делиться a. Если a на него делится, а b - нет, то мы выходим из цикла и печатаем -1. В противном случае если n меньше отношения, будем говорить, $https://www.cyberforum.ru/cgi-bin/latex.cgi?\alpha$ _{A_i} к $https://www.cyberforum.ru/cgi-bin/latex.cgi?\alpha$ _{B_i}, округленному вверх, то присваиваем n это значение. Теперь. Когда-то мы можем дойти до значения cicadacand, равного составному числу. К этому моменту мы уже поделили A и B на простые множители этого составного числа, поэтому они на него делиться не будут.

Новые блоги и статьи Все статьи Все блоги /
тв 16 бой ии anaschu 27.07.2026 Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .	мв 15. непроверенное, возможно, глюк anaschu 27.07.2026 НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .	Очистка реквизитов и табличных частей документа при копировании Maks 26.07.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .	Доктрина интенционального знания - Доктрина для портала "Срез". Hrethgir 25.07.2026 Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .
сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых anaschu 25.07.2026 Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.	сукцессия 43. Вторая научная статья за месяц- прайминг и гатгил anaschu 25.07.2026 две стороны одной монеты	Более приземисто - Эстафету хвоста в .cdl (деревья эстафеты в сад). Hrethgir 24.07.2026 В будущем, после написания блока инверсии обхода дерева (эстафеты хвоста), я планирую вернуться к нашему прошлому разговору о том, обладают ли знания целеполаганием. Тогда я пришел к выводу, что. . .	Вот представьте что вам дали бессмертие. kumehtar 24.07.2026 Вот представьте что вам дали бессмертие, ничего более не меняя. Вообще ничего, только бессмертие в нынешнем виде. Рады были бы? Что бы вы тут делали всё это время? Никакой пенсии. Никакого нового. . .

@Senjey 0 / 0 / 0 Регистрация: 09.02.2019 Сообщений: 8
	31.08.2020, 11:57
	dfgdfghfhvhvh, "Ответ - 2" имелось ввиду просто 2. 21*21(441) кратно 9 !!!! Как раз это правильный ответ 0

@dfgdfghfhvhvh 0 / 0 / 0 Регистрация: 24.04.2019 Сообщений: 5
	31.08.2020, 12:56
	Gdez, вы неправильно понимаете алгоритм программы, которая написана мной выше. cicadacand - число, на которое может делиться a. Если a на него делится, а b - нет, то мы выходим из цикла и печатаем -1. В противном случае если n меньше отношения, будем говорить, $https://www.cyberforum.ru/cgi-bin/latex.cgi?\alpha$ _{A_i} к $https://www.cyberforum.ru/cgi-bin/latex.cgi?\alpha$ _{B_i}, округленному вверх, то присваиваем n это значение. Теперь. Когда-то мы можем дойти до значения cicadacand, равного составному числу. К этому моменту мы уже поделили A и B на простые множители этого составного числа, поэтому они на него делиться не будут. 0