1520. Нечетные делители
Пусть f(n) – наибольший
нечетный делитель натурального числа n.
Для заданного натурального числа n вычислите
значение суммы f(1) + f(2) + ... + f(n).
Вход. Каждая строка содержит одно натуральное число n (n
≤ 109).
Выход. Для каждого значения
n выведите в отдельной строке значение
суммы f(1) + f(2) + ... + f(n).
|
Пример
входа |
Пример
выхода |
|
7 1 777 |
21 1 201537 |
РЕШЕНИЕ
рекурсия
Анализ алгоритма
Если число n
нечетное, то f(n) = n. Если число n
четное, то f(n) = f(n / 2).
Пусть g(n)
= f(1) + f(2)
+ ... + f(n). Разобьем множество натуральных чисел от 1 до n на два подмножества: нечетных ODD и
четных EVEN чисел.
Среди
натуральных чисел от 1 до n имеется в
точности
k = 
нечетных и l
= 
четных чисел
Тогда f(1) + f(3)
+ f(5)
+ ... + f(2k – 1) = 1 + 3 + 5 + … + (2k
– 1) =
= k2
В то же время f(2) + f(4)
+ f(6)
+ ... + f(2l) = f(1) + f(2) +
f(3) + ... + f(l)
=
g(l) = 
Для окончания
рекурсии положим g(0) = 0. Таким образом
Пример
Рассмотрим
первый тест, в котором n = 7.
Среди
натуральных чисел от 1 до 7 имеется в точности k
= 
= 4 нечетных и l
= 
= 3 четных числа.
g(7) = 
+ 
= 16 + g(3) =
16 + 
+ 
= 16 + 4 + g(1) = 16 +
4 + 1 = 21
Реализация алгоритма
Реализация функции g приведена ниже.
long long
g(long long n)
{
long long k = (n + 1) / 2;
if (n == 0) return 0;
return k * k
+ g(n / 2);
}
Основная часть программы. Читаем
значение n и выводим g(n).
while(scanf("%lld",&n)
== 1)
printf("%lld\n",g(n));
Java реализация
import java.util.*;
public class Main
{
static long g(long n)
{
long k = (n + 1) / 2;
if (n == 0) return 0;
return k * k + g(n / 2);
}
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
while(con.hasNext())
{
long n = con.nextLong();
System.out.println(g(n));
}
}
}