Суперстепень

@CodeKing · Регистрация: 07.11.2019

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

Даны натуральные числа a, b, c и m (a ≤ 9, b ≤ 9, c ≤ 9, m ≤ 10000). Кто-то выписал на доске все возможные сверхстепени, составленные из чисел a, b и c по модулю m (то есть abc mod m, acb mod m, bac mod m и так далее).

Чему равно наибольшее из выписанных чисел?

@Holiday13 · 10.11.2019, 12:13

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
    int a[3],m;
    cout<<"a b c m:";
    cin>>*a>>a[1]>>a[2]>>m;
    int mx=0;
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)
        if(j!=i)
            for(int k=0; k<3; k++)
            if(k!=i && k!=j)
            {
                int dm=(a[i]*100+a[j]*10+a[k])%m;
                if(mx<dm) mx=dm;
            }
    cout<<mx<<endl;

@CodeKing · 10.11.2019, 12:38 **[ТС]**

Holiday13, К сожалению ответ не верный(
Например:
Входные данные
1 2 3 7
Результат работы
3

@Holiday13 · 10.11.2019, 12:43

132 mod 7 = ?

@CodeKing · 10.11.2019, 12:47 **[ТС]**

Holiday13, Блин виноват.Там должно быть a^b^c и т д.

Байт · 10.11.2019, 13:35

CodeKing, Над ответом есть значок X²
Должно получиться так a^{b^c}
А записывается так
a[SUP]b[SUP]c[/SUP][/SUP]

Добавлено через 12 минут
Верхнюю степень, чтобы не залезать в дебри алгебры, придется считать по-честному. Что для чисел <= 9 не страшно.
А вот последнее возведение - можно просто все умножения делать по модулю m (умножил, и тут же %m его)
Для увеличения скорости (9⁹) все-таки большое число) возводить в степень следует делением пополам. Рекурсивно это будет выглядеть так

C++
1
2
3
4
5
6
7
8
9
10
int powm(int x, int y, int m)
{
   if (y==0) return 1;  
   if (y==1) return x;
   if (x==1 || x==0) return x; // При работе "по-модулю" случай нередкий
   int r = powm(x, y/2, m) %m;
   r = r*r%m;
   if (y%2) r = r*x%m;
   return r;
}

Добавлено через 9 минут
Предупреждение! При вычислении степеней здесь ни в коем случае нельзя пользоваться функцией pow!

@CodeKing · 10.11.2019, 19:34 **[ТС]**

Байт, Это решение задачи,или просто как я понял возведение (x в степень y )%m.

Байт · 10.11.2019, 20:03

Сообщение от CodeKing

просто как я понял возведение (x в степень y )%m.

Да, просто возведение. Это как бы вычислительное ядро задачи. Имхо, остальное не должно представлять особого труда даже для начинающего (но уже начавшего). Или у тебя есть сложности?
Там еще перебор всех 6-ти перестановок надо сделать. Но с этим код уважаемого Holiday13 в посте 2 справляется. Чуток не то считает, но это ты сам виноват...

Вообще-то для перебора всех перестановок есть красивые алгоритмы, но для 3-х элементов и так сойдет

Байт · 12.11.2019, 21:58

Сообщение от Байт

Верхнюю степень, чтобы не залезать в дебри алгебры, придется считать по-честному.

Но я, простите, недооценил природную человечью любознательность И народ волнуется

Залезть в дебри было бы тоже интересно.

Давайте попробуем, хотя я не обладаю необходимой компетенцией, чтобы говорить уверенно.
Но дело вот в чем. будем считать a^xпо модуля m, перебором x. Ясно, что результаты будут повторяться (принципа Дирихле никто не отменял) Вопрос - когда? Если мы найдем точку повторения (k), то ясно. что нам нужен только остаток от деления b^c на k. А вот тут в бой вступает Малая теорема Ферма (она на то и малая, что в отличии от БТФ просто доказуема, что легко сделал Эйлер, да и любознательному школьнику она не составит большого труда), функция того же Эйлера и прочие чудесные штучки. Самое смешное, что все эти штучки легко программируются, они алгоритмичны.
Этот подход может снять ограничения a, b, c <= 9
Удачи тем, кому это интересно!

Новые блоги и статьи Все статьи Все блоги /
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение/ Перевод https:/ / **********/ gallery/ thinkpad-x220-tablet-porn-gzoEAjs . . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .

@CodeKing 67 / 1 / 0 Регистрация: 07.11.2019 Сообщений: 56

	Суперстепень 10.11.2019, 11:47. Показов 4081. Ответов 8 Метки нет (Все метки) Даны натуральные числа a, b, c и m (a ≤ 9, b ≤ 9, c ≤ 9, m ≤ 10000). Кто-то выписал на доске все возможные сверхстепени, составленные из чисел a, b и c по модулю m (то есть abc mod m, acb mod m, bac mod m и так далее). Чему равно наибольшее из выписанных чисел? 0

@CodeKing 67 / 1 / 0 Регистрация: 07.11.2019 Сообщений: 56
	10.11.2019, 12:38 [ТС]
	Holiday13, К сожалению ответ не верный( Например: Входные данные 1 2 3 7 Результат работы 3 0

@Holiday13 Заблокирован
	10.11.2019, 12:43
	132 mod 7 = ? 0

@CodeKing 67 / 1 / 0 Регистрация: 07.11.2019 Сообщений: 56
	10.11.2019, 12:47 [ТС]
	Holiday13, Блин виноват.Там должно быть a^b^c и т д. 0

@CodeKing 67 / 1 / 0 Регистрация: 07.11.2019 Сообщений: 56
	10.11.2019, 19:34 [ТС]
	Байт, Это решение задачи,или просто как я понял возведение (x в степень y )%m. 0