Непарні дільники#1520

Непарні дільники (Розбір)

Якщо число $n$ непарне, то $f (n) = n$ f(n) = n.

Якщо число $n$ парне, то $f (n) = f (n /2)$ f(n) = f(n / 2).

Нехай

g (n) = f (1) + f (2) + ... + f (n)

g(n) = f(1) + f(2) + ... + f(n)

Розглянемо розбиття множини натуральних чисел від $1$ до $n$ на два підмножини:

ODD — множина непарних чисел,
EVEN — множина парних чисел.

Серед натуральних чисел від $1$ до $n$ є рівно:

$k = ⌊ (n + 1) /2 ⌋$ k = \left\lfloor (n + 1) / 2 \right\rfloor непарних
$l = ⌊ n /2 ⌋$ l = \left\lfloor n / 2 \right\rfloor парних чисел

Тоді:

f (1) + f (3) + f (5) + ... + f (2 k - 1) = 1 + 3 + 5 + \dots + (2 k - 1) = \frac{1 + 2 k - 1}{2} \cdot k = k^{2}

f(1) + f(3) + f(5) + ... + f(2k - 1) = \\ 1 + 3 + 5 + … + (2k - 1) = \\ {1 +2k - 1\over 2} \cdot k = k^2

В той же час:

f (2) + f (4) + f (6) + ... + f (2 l) = f (1) + f (2) + f (3) + ... + f (l) = g (l) = g (⌊ n /2 ⌋)

f(2) + f(4) + f(6) + ... + f(2l) = \\ f(1) + f(2) + f(3) + ... + f(l) = \\ g(l) = g(\left\lfloor n / 2 \right\rfloor)

Для завершення рекурсії покладемо $g (0) = 0$ g(0) = 0. Таким чином:

g (n) = {k^{2} + g (⌊ n /2 ⌋), k = (⌊ n + 1) /2 ⌋ 0, n = 0

g(n) = \begin{cases} k^2 + g(\left\lfloor n / 2 \right\rfloor), k = (\left\lfloor n + 1) / 2 \right\rfloor \\ 0, n = 0 \end{cases}

Приклад

Розглянемо перший тест, у якому $n = 7$ n = 7.

Серед натуральних чисел від $1$ до $7$ є точно:

$k = ⌊ (7 + 1) /2 ⌋ = 4$ k = \left\lfloor (7 + 1) / 2 \right\rfloor = 4 непарних числа;
$l = ⌊ 7/2 ⌋ = 3$ l = \left\lfloor 7 / 2 \right\rfloor = 3 парних числа.

g (7) = ⌊ \frac{7 + 1}{2} ⌋^{2} + g (⌊ \frac{7}{2} ⌋) = 16 + g (3) = 16 + ⌊ \frac{3 + 1}{2} ⌋^{2} + g (⌊ \frac{3}{2} ⌋) = 16 + 4 + g (1) = 16 + 4 + 1 = 21

g(7) = \left\lfloor 7 + 1 \over 2 \right\rfloor^2 + g\left(\left\lfloor 7 \over 2 \right\rfloor\right) = 16 + g(3) = \\ 16 + \left\lfloor 3 + 1 \over 2 \right\rfloor^2 + g\left(\left\lfloor 3 \over 2 \right\rfloor\right) = 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));
    }
  }
}

Java

Python реалізація

Реалізуємо функцію g.

def g(n):
  if n == 0:
    return 0
  k = (n + 1) // 2
  return k * k + g(n // 2)

Основна частина програми. Для кожного тесту читаємо вхідне значення $n$ та виводимо $g (n)$ .

for line in sys.stdin:
  n = int(line)
  print(g(n))