Обратное число

14.10.2020, 20:53. Показов 10997. Ответов 0

Метки нет (Все метки)

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

Даны два целых числа m и a. Если не существует обратного числа к a по модулю m, то выведите число −1, а если существует, то выведите это число (ответ должен лежать в границах от 0 до m−1).

Входные данные:

В единственной строке входных данных даны два целых числа 1<m≤10⁹ и 0<a<m.

Выходные данные:

Выведите ответ на задачу.

Программа не проходит тест с ошибкой: неверный ответ. Помогите найти ошибку в коде.

Вот мой код:

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
25
26
27
28
29
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a
 
numbers = list(map(int, input().split()))
 
m = numbers[0]
n = numbers[1]
 
def euler(x):
    res = x
    i = 2
    while i * i <= x:
        if x % i == 0:
            while x % i == 0:
                x = x // i
                res -= res // i
        i += 1
    if x > 1:
        res -= res // x
    return res
 
if gcd(m, n) == 1:
    p = euler(m) - 1
    ans = pow(n, p, m)
    print(ans)
else:
    print(-1)

Добавлено через 3 часа 55 минут
нашел ошибку. поставил res -= res//i в цикл, хотя он должен относиться к блоку if

Python
1
2
3
4
5
6
7
8
9
10
11
12
def euler(x):
    res = x
    i = 2
    while i * i <= x:
        if x % i == 0:
            while x % i == 0:
                x = x // i
            res -= res // i
        i += 1
    if x > 1:
        res -= res // x
    return res

cpp_developer

Эксперт

20123 / 5690 / 1417

Регистрация: 09.04.2010

Сообщений: 22,546

Блог

14.10.2020, 20:53

Ответы с готовыми решениями:

Обратное число
Напишите программу, которая считывает с клавиатуры одно дробное число и выводит обратное ему. Если при этом введённое с клавиатуры число...

Обратное число
Напишите программу, которая считывает с клавиатуры одно число и выводит обратное ему. Если при этом введённое с клавиатуры число – ноль, то...

Обратное число
Обратное число В этой задаче нужно ответить на 1≤t≤105 запросов. Каждый запрос состоит из двух целых чисел 2≤p≤109 и 0<a<p, число p...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

raxper

Эксперт

30234 / 6612 / 1498

Регистрация: 28.12.2010

Сообщений: 21,154

Блог

14.10.2020, 20:53

Помогаю со студенческими работами здесь

Обратное число
Помогите, моя программы по мнению тестовой системы Сириуса работает слишком долго. Помогите ускорить мою программу. Вот само задание: ...

Обратное число
Даны два целых числа m и a. Если не существует обратного числа к a по модулю m, то выведите число −1, а если существует, то выведите это...

Обратное число
Обратное число В этой задаче нужно ответить на 1≤t≤105 запросов. Каждый запрос состоит из двух целых чисел 2≤p≤109 и 0<a<p, число p...

Обратное число, задача
Здравствуйте! Есть задача, которая вроде бы легкая,но мое решение не засчитывают. Говорят, что превышено время работы(5 секунд - максимум)....

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:

Новые блоги и статьи Все статьи Все блоги /
Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .
Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .

Наверх