Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
Alemano
0 / 0 / 0
Регистрация: 03.10.2015
Сообщений: 23
1

Найти все целые числа X в диапазоне [0, M – 1], такие что X^N mod M = Y

03.10.2015, 13:20. Просмотров 957. Ответов 8
Метки нет (Все метки)

...Напишите программу, которая найдёт все целые числа X в диапазоне [0, M – 1], такие что X^N mod M = Y.

Исходные данные
Ввод содержит единственную строку с числами N, M и Y (0 < N < 999, 1 < M < 999, 0 < Y < 999), записанными через пробел.

Результат
Выведите все числа X через пробел в одной строке. Числа должны идти в порядке возрастания. Если искомых чисел нет, выведите −1.

Помогите, пожалуйста. Находил решение этой задачи на паскале, но ничего не понял. Заранее, спасибо
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.10.2015, 13:20
Ответы с готовыми решениями:

Используя перебор значений найти все такие целые a, b, что n=3a+5b для любого натурального n>7
Помогите с задачей,пожалуйста.

Дано целое число N. Найдите все такие целые числа d, что N делится на d2 и не делится на d3.
Вроде все норм работает, по крайней мере числа находит, но почему-то если ввожу...

В квадратный числовой массив записаны целые числа в диапазоне от -99 до 99. Определить, имеются ли такие квадратные подмассивы, сумма элементов которы
В квадратный числовой массив записаны целые числа в диапазоне от -99 до 99....

Найти все такие числа k, что k-я строка совпадает с k-м столбцом. Найти наибольший элемент главной диагонали
Найти все такие числа k, что k-я строка совпадает с k-м столбцом. Найти...

Вывести все целые числа в заданном диапазоне
Ребят, нужна помощь, только начали c++ и уже завал. Нужна программа, которая...

8
zss
Модератор
Эксперт С++
7178 / 6677 / 4226
Регистрация: 18.12.2011
Сообщений: 17,619
Завершенные тесты: 1
03.10.2015, 13:49 2
C++
1
2
3
4
5
6
7
8
9
10
11
int pow(int x,int n)
{
    int p=1;
    for(int i=1;i<=n;i++)
       p*=x;
    return p;
}
...
for(int X=0;X<M;X++)
   if( pow(X,N)%M==Y)
     cout<<X<<" ";
0
Байт
Эксперт C
18318 / 12029 / 2506
Регистрация: 24.12.2010
Сообщений: 24,293
03.10.2015, 13:57 3
zss, могу предложить в функции pow сразу вычислять по модулю M. А если пользоваться вашим кодом, то как вы себе представляете 988988?
1
zss
Модератор
Эксперт С++
7178 / 6677 / 4226
Регистрация: 18.12.2011
Сообщений: 17,619
Завершенные тесты: 1
03.10.2015, 14:33 4
Байт, Не думаю, что ТС надо так глубоко копать.
0
Байт
Эксперт C
18318 / 12029 / 2506
Регистрация: 24.12.2010
Сообщений: 24,293
03.10.2015, 15:11 5
Лучший ответ Сообщение было отмечено Alemano как решение

Решение

Цитата Сообщение от zss Посмотреть сообщение
Не думаю, что ТС надо так глубоко копать.
Однако, ваш код при заданных ограничениях просто не будет работать, т.е. работать-то он будет, но выдавать будет ахинею
Давайте подправлю.
C++
1
2
3
4
5
6
7
8
9
10
11
int powBait(int x, int n, int m)
{
    int p=1;
    for(int i=1;i<=n;i++)
       p = (x*p)%m;
    return p;
}
...
for(int X=0;X<M;X++)
   if( powBait(X,N,M)==Y)
     cout<<X<<" ";
2
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
03.10.2015, 15:54 6
Байт, только надо возвращать не p, а p % m в функции powBait;
0
Байт
Эксперт C
18318 / 12029 / 2506
Регистрация: 24.12.2010
Сообщений: 24,293
03.10.2015, 15:58 7
Цитата Сообщение от SlavaSSU Посмотреть сообщение
надо возвращать не p, а p % m в функции powBait;
Зачем? Он уже приведен по модулю m в процессе вычислений
0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
03.10.2015, 16:02 8
Байт, затем, что при n == 0, он не зайдет в цикл и p останется равным 1, и если m == 1 то ответ 0, а не 1.

Ой. там все числа строго больше нуля во входе...
1
Байт
Эксперт C
18318 / 12029 / 2506
Регистрация: 24.12.2010
Сообщений: 24,293
03.10.2015, 16:33 9
SlavaSSU, Ваша правдочка!
Тогда предлагаю строчку 3
C++
1
p = 1%m;
Или
C++
1
if (m==1) return 0;
Но, конечно, можно и как вы предлагаете.

Добавлено через 24 минуты
Цитата Сообщение от SlavaSSU Посмотреть сообщение
Ой. там все числа строго больше нуля во входе...
Ну, значит наш код решает более общую задачу
0
03.10.2015, 16:33
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.10.2015, 16:33

Вывести все целые числа в определенном диапазоне
Подскажите пожалуйста по решению задачи Задача: Напишите программу, которая...

Найти все трехзначные числа, такие, что сумма цифр равна А, а само число делиться на B
помоги плиз, составить программу вывода кубов от 1 до 25, подсчитать их сумму

Найти все трехзначные числа, такие, что сумма цифр равна А, а само число делится на B
помогите


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru