Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
GoldenId
89 / 130 / 32
Регистрация: 11.11.2010
Сообщений: 770
Записей в блоге: 14
Завершенные тесты: 1
#1

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

06.06.2017, 07:57. Просмотров 204. Ответов 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, 456B - Федя и математика (C++):

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

Codeforces.Double Cola - C++
Условие задачи таково: Шелдон, Леонард, Пенни, Раджеш и Говард стоят в очереди к автомату по продаже баночек с напитком «Double Cola»,...

Codeforces и питон - Python
Не могу разобраться, как осуществляется ввод и вывод данных. Вводные данные:В первой строке расположены два целых числа A и B, не...

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

с++ и математика - C++
Здравствуйте. Как написать на си это?

Математика... - C++ Builder
Добрый день! Возникла трудность: Что-то не получается правильно записать код о выводе об ошибке... Проверте, может чего не...

1
GoldenId
89 / 130 / 32
Регистрация: 11.11.2010
Сообщений: 770
Записей в блоге: 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
Привет! Вот еще темы с ответами:

математика - Математика
Доброго времени суток!!! помогите пожалуйста с задачами. не могу закрыть сессию. математика единственный не закрытый предмет. Прошу...

Математика - C#
Ребят помогите надо сделать 3 программы. 1. Определение функции по ее введенному виду. 2. Расчет производной в точке. 3.Сумма...

Математика в qt - C++ Qt
Всем доброго времени суток. Не понимаю почему qt неправильно делит одно число на другое:( void paint::mousePressEvent(QMouseEvent...

Математика - C++
ПОмогите пожалуйста понять Square - квадрат, который характеризуется координатами левого верхнего угла и длиной стороны Rectangle -...


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

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

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