Дам 30 б.! Задача 2. Остаток от деления (циклы использовать нельзя, не уложитесь по времени)
Ограничение по времени: 2 с
Написать программу, которая находит остаток от деления числа 2²¹ + 2²² + ... + 2²n-1(в степени 2n-1) + 2²n( в степени 2n) на 7.
Напомним, что 2N — это произведение N множителей, каждый из которых равен 2, а 22N = 2(2N)
Входные данные
вводится натуральное число N < 100000
Выходные данные
Вывести на экран одно число — остаток от деления
число разбиваем на суммы слагаемых степеней числа 2 (например, число 99=64+35=64+32+3=64+32+2+1=2^6+2^5+2^1+2^0=1100011(2) )
2) делим на 2, пока не получим число меньше 2 то есть 1 (дробная часть отбрасывается)
513 256 128 64 32 16 8 4 2 1 если четно внизу пишем 0 иначе 1
1 0 0 0 0 0 0 0 0 1 собираем цифры с конца на начало
513=1000000001 (2)
3) 513 | 2
512|
1 256 | 2
256 |
0 128 | 2
128 |
0 64 | 2
64 |
0 32 | 2
32 |
0 16 | 2
16 |
0 8 | 2
8 |
0 4 | 2
4 |
0 2 | 2
2 |
0 1
Собираем остатки при вычитании 0 и 1 с конца до начала
Еще вариант на калькуляторе (для проверки)
1 - 3бит
2 - 128 цветов
3 - 512Кбайт
4 - ≈1406,25 Кбайт
Объяснение:
Напишем формулы, необходимые для решения задач:
1. N = 2^I , где N - кол-во цветов в палитре, I - глубина цвета
2. V = a*I , где V - информационный объем, a - количество пикселей
Задача 1
Воспользуемся формулой 1 и выведем I
I = log2 N = I = log2 8 = 3бит
Задача 2
Воспользуемся формулой 1
N = 2^I = 2^7 = 128 цветов
Задача 3
Воспользуемся формулой 2
V = a*I = 1024*512*8 бит / 2^13 = 2^10 * 2^9 * 2^3 / 2^13 = 2^9 Кбайт = =512Кбайт
Задача 4
Воспользуемся формулой 1 и формулой 2
Выведем I из формулы 1:
I = log2 N = log2 16*10^6 = log2 2^4*10^6 = 2*log2 2^2*10^3 =
= 2*log2 4000 ≈ 2*12 = 24бит
V = a*I = 800*600*24/2^13 = 2^3 * 10^2 * 2*3 * 10^2 * 2^3 * 3 / 2^13 =
= 2^7 * 10^4 * 3^2 / 2^13 = 2^11 * 5^4 * 3^2 / 2^13 = 5^4 * 3^2 / 2^2 =
= 625*9/4 = 1406,25 Кбайт