Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
GoldenId
131 / 130 / 64
Регистрация: 11.11.2010
Сообщений: 771
Записей в блоге: 14
Завершенные тесты: 1
1

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

06.06.2017, 07:57. Просмотров 258. Ответов 1
Метки нет (Все метки)

Страница задачи на codeforces.com

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

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

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

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


Ход мысли
Сначала я думал вычислять значения степеней 2n mod 5, 3n mod 5, 4n mod 5 бинарным возведением в степень по модулю... Но число n - слишком уж большое. Его в общем случае не зачитаешь в числовую переменную.
Завёл лист в Excel и посчитал значения для первых n.
n1n%52n2n%53n3n%54n4n%5sumsum%5
0111111144
11223344100
214494161100
3183272644100
41161811256144
51322243310244100
61644729440961100
71128321872163844100
8125616561165536144
9151221968332621444100
1011024459049410485761100
11120483177147241943044100
12140961531441116777216144
1318192215943233671088644100
141163844478296942684354561100
15132768314348907210737418244100
1616553614304672114294967296144
Оказалось, что каждое слагаемое и сумма повторяется с периодом 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;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.06.2017, 07:57
Ответы с готовыми решениями:

Задача с Codeforces, уровень A
Вроде простая задача, а я затупил. Неправильный ответ на тесте 5 Ограбление...

Codeforces.Double Cola
Условие задачи таково: Шелдон, Леонард, Пенни, Раджеш и Говард стоят в очереди...

Runtime error в задаче на codeforces
(p.s. что за тупая система тут: написал пост , не зная, что слово &quot;проблема&quot; в...

Codeforces и питон
Не могу разобраться, как осуществляется ввод и вывод данных. Вводные данные:В...

Нахождение суммы остатков (задача с Codeforces)
Здравствуйте! Сейчас я пытаюсь решить задачу. Суть такая - даются числа n и m,...

1
GoldenId
131 / 130 / 64
Регистрация: 11.11.2010
Сообщений: 771
Записей в блоге: 14
Завершенные тесты: 1
06.06.2017, 08:07  [ТС] 2
Разбор
На удивление в разборе оба предложенных решения сложнее.


Кто шарит, объясните преобразования:
Codeforces, 456B - Федя и математика

Как они сделали первое преобразование, и что за такая http://www.cyberforum.ru/cgi-bin/latex.cgi?\phi \left(n \right)?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.06.2017, 08:07

Математика и С++
Всем здрасте,сразу скажу что не знал куда написать. Изучяю сейчас С++, и...

Математика...
Добрый день! Возникла трудность: Что-то не получается правильно записать...

С++ и математика
Задание вот это Чтобы открыть сейф, нужно ввести код – число, состоящее из...


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

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

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