Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
Zadr
0 / 0 / 1
Регистрация: 07.12.2015
Сообщений: 33
1

Задача Новый год и старые свойства длинная арифметика

30.12.2015, 20:14. Просмотров 1165. Ответов 1
Метки нет (Все метки)

Здраствуйте помогите пожалуйста с задачой!
Вроде бы длинная арифметика!
Нужно решить ее срочно!
Помогите чем сможете пожалуйста!

B. Новый год и старые свойства
ограничение по времени на тест2 секунды
ограничение по памяти на тест256 мегабайт
вводстандартный ввод
выводстандартный вывод
2015 год почти подошёл к концу.

Лимак — белый медвежонок, который недавно узнал о двоичной системе счисления. Он сразу заметил, что запись номера прошедшего года в двоичной системе счисления содержит ровно один ноль — 201510 = 111110111112. Обратите внимание, количество нулей в записи числа в десятичной системе счисления значения не имеет.

Лимак выбрал некоторый интервал лет и теперь собирается посчитать количество лет из этого интервала, таких что их запись в двоичной системе счисления так же содержит ровно один ноль. А сможете ли вы сделать это быстрее?

Считайте, что положительные целые числа всегда записываются без ведущих нулей.

Входные данные
В единственной строке входных данных записаны два целых числа a и b (1 ≤ a ≤ b ≤ 1018) — первый и последний год в интервале Лимака, соответственно.

Выходные данные
Выведите одно целое число — количество лет в данном интервале, запись которых в двоичной системе счисления содержит ровно один ноль.

Примеры тестов

входные данные

5 10

выходные данные

2

входные данные

2015 2015

выходные данные

1

входные данные

100 105

выходные данные

0

входные данные

72057594000000000 72057595000000000

выходные данные

26

Примечание

В первом примере интервал Лимака содержит числа 510 = 1012, 610 = 1102, 710 = 1112, 810 = 10002, 910 = 10012 и 1010 = 10102. Два из них (1012 и 1102) обладают описанным выше свойством.
0
Лучшие ответы (1)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.12.2015, 20:14
Ответы с готовыми решениями:

Длинная арифметика. Задача А + В
Прошу помочь решить эту задачку, желательно с закомментированными построчными объяснениями. ...

Задача на почти факториал. F(n)=n*F(n-1)*F(n-2). Длинная арифметика
Здравствуйте. Помогите пожалуйста реализовать задачу. F(n)=n*F(n-1)*F(n-2) F(1)=1. От факториала...

Длинная арифметика
Тема Длинная арифметика. На языке Паскаль. Условие:Составить прогу для вычисления точного...

Длинная арифметика
нужен текст програмы на С, в которой был бы реализован алгоритм ввода-вывода длинного числа,...

1
Dmitriy_73
3 / 3 / 5
Регистрация: 20.05.2014
Сообщений: 12
Завершенные тесты: 10
30.12.2015, 21:56 2
Лучший ответ Сообщение было отмечено Zadr как решение

Решение

Не нужна тут длинная арифметика. Число имеет в своей двоичной записи один ноль , если оно имеет вид https://www.cyberforum.ru/cgi-bin/latex.cgi?  {2}^{n} \ -  \ 1 \ -  \ {2}^{k}; \ 0 \leq k \leq n - 2

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
int main() {
    long long a, b;
    int ans = 0;
    std::cin >> a >> b;
    for(int i = 2; i < 61 ; ++i){
        for(int j = 0; j < i - 1; ++j) {
            long long tmp = (1ll << i) - 1 - (1ll << j);
            if (a <= tmp && tmp <= b){
                ans++;
            }
        }
    }
    std::cout << ans;
    return 0;
}
0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.12.2015, 21:56

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Длинная арифметика))
Программка уже почти готова, единственное неправильно находит остаток при делении По заданию:...

Длинная арифметика
Алгоритмы всех операций в принципе уже готовы (длина числа ограничивается только ресурсами ПК)....

Длинная арифметика
Встречаются ли среди цифр числа (2 в степени 11213 – 1) две подряд идущие девятки? помогите...

Длинная арифметика
Необходимо написать программу по переводу числа длиной до 50-и символов из десятичной в двоичною...


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

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

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