Codeforces, 456B - Федя и математика

@GoldenId · Регистрация: 11.11.2010

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

Условие

Федя учится в гимназии. Домашнее задание по математике у Феди состоит в вычислении следующего выражения:

(1ⁿ + 2ⁿ + 3ⁿ + 4ⁿ) mod 5
для заданного числа n. Федя смог выполнить это задание. А сможете ли вы? Обратите внимание, что заданное число n может быть очень большим (например, оно может не помещаться в целочисленные типы вашего языка программирования).

Входные данные
В единственной строке находится целое число n (0 ≤ n ≤ 10^10⁵). Число не содержит лидирующих нулей.

Выходные данные
Выведите значение выражения без лидирующих нулей.

Ход мысли

Сначала я думал вычислять значения степеней 2ⁿ mod 5, 3ⁿ mod 5, 4ⁿ mod 5 бинарным возведением в степень по модулю... Но число n - слишком уж большое. Его в общем случае не зачитаешь в числовую переменную.
Завёл лист в Excel и посчитал значения для первых n.

n	1ⁿ%5	2ⁿ	2ⁿ%5	3ⁿ	3ⁿ%5	4ⁿ	4ⁿ%5	sum	sum%5
0	1	1	1	1	1	1	1	4	4
1	1	2	2	3	3	4	4	10	0
2	1	4	4	9	4	16	1	10	0
3	1	8	3	27	2	64	4	10	0
4	1	16	1	81	1	256	1	4	4
5	1	32	2	243	3	1024	4	10	0
6	1	64	4	729	4	4096	1	10	0
7	1	128	3	2187	2	16384	4	10	0
8	1	256	1	6561	1	65536	1	4	4
9	1	512	2	19683	3	262144	4	10	0
10	1	1024	4	59049	4	1048576	1	10	0
11	1	2048	3	177147	2	4194304	4	10	0
12	1	4096	1	531441	1	16777216	1	4	4
13	1	8192	2	1594323	3	67108864	4	10	0
14	1	16384	4	4782969	4	268435456	1	10	0
15	1	32768	3	14348907	2	1073741824	4	10	0
16	1	65536	1	43046721	1	4294967296	1	4	4

Оказалось, что каждое слагаемое и сумма повторяется с периодом 4. А именно
Если n кратно 4, то ответ 4, иначе - 0.
Признак делимости числа на 4 в десятичной система счисления - чтобы число из последних двух его цифр делилось на 4.
То есть для реализации достаточно выкинуть все лидирующие цифры, кроме двух (или взять одну, если есть только она)
и посмотреть, делится ли число из них на 4 без остатка.

Код

К удивлению долго не получалось справиться с чтением двух символов. В частности встроенный редактор Code::Blocks упорно дописывал в файл input.txt завершающий '\n', из-за чего условие

C++
1
while( is.peek() != EOF )

срабатывало неправильно, один лишний раз. В итоге победилось следующим образом:

C++
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
30
31
32
33
34
35
36
37
//#define CF
#include <cstddef>
#ifdef CF
#include <iostream>
#else
#include <fstream>
#endif
 
int main()
{
#ifdef CF
    std::istream& is = std::cin;
    std::ostream& os = std::cout;
#else
    std::ifstream is( "input.txt" );
    std::ofstream os( "output.txt" );
#endif // CF
 
    char ch1, ch2;
    bool one = true;
    is >> ch1;
    if( isdigit( is.peek() ) )
    {
        one = false;
        is >> ch2;
    }
    while( isdigit( is.peek() ) )
    {
        ch1 = ch2;
        is >> ch2;
    }
    if( one && ( ch1 - '0' ) % 4 == 0
        || !one && ( ( ch1 - '0' )*10 + ( ch2 - '0' ) ) % 4 == 0 )
        os << 4;
    else
        os << 0;
}

@GoldenId · 06.06.2017, 08:07 **[ТС]**

Разбор

На удивление в разборе оба предложенных решения сложнее.

Кто шарит, объясните преобразования:

Как они сделали первое преобразование, и что за такая $https://www.cyberforum.ru/cgi-bin/latex.cgi?\phi \left(n \right)$ ?

Новые блоги и статьи Все статьи Все блоги /
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 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@GoldenId 142 / 143 / 64 Регистрация: 11.11.2010 Сообщений: 877 Записей в блоге: 10
	06.06.2017, 08:07 [ТС]
	Разбор На удивление в разборе оба предложенных решения сложнее. Кто шарит, объясните преобразования: Как они сделали первое преобразование, и что за такая $https://www.cyberforum.ru/cgi-bin/latex.cgi?\phi \left(n \right)$ ? 0