1520. Odd Divisors
Let f(n) be the greatest odd divisor of n, where n is a positive
integer. You are given a positive integer n.
Find the sum f(1) + f(2) + ... + f(n).
Input. Each line
contains one positive integer n (n ≤ 109).
Output.
For each value of n print in a
separate line the value of f(1) + f(2) + ... + f(n).
|
Sample
input |
Sample
output |
|
7 1 777 |
21 1 201537 |
SOLUTION
recursion
Algorithm analysis
If n is odd, then f(n)
= n. If n is even, then f(n)
= f(n / 2).
Let g(n) = f(1) + f(2)
+ ... + f(n). Divide the set of positive integers from 1 to n into two subsets: odd ODD = {1, 3, 5,
…, 2k – 1} and even EVEN = {2, 4, 6,
…, 2l} numbers.
Among the positive integers
from 1 to n there are exactly
k = 
odd and l
= 
even numbers
Then f(1) + f(3)
+ f(5)
+ ... + f(2k – 1) = 1 + 3 + 5 + … + (2k
– 1) =
= k2
At the same time f(2) + f(4)
+ f(6)
+ ... + f(2l) = f(1) + f(2) +
f(3) + ... + f(l)
=
g(l) = 
To stop the recursion we
assume that g(0) = 0. So
Example
Consider the first test
case, where n = 7.
Among the positive integers
from 1 to 7 there are exactly k = 
= 4 odd and l = 
= 3 even numbers.
g(7) = 
+ 
= 16 + g(3) =
16 + 
+ 
= 16 + 4 + g(1) = 16 +
4 + 1 = 21
Algorithm
realization
The realization of function g is
given below.
long long g(long long n)
{
long long k = (n + 1) / 2;
if (n == 0) return 0;
return k * k
+ g(n / 2);
}
The main part of the program. Read the value of n and print g(n).
while(scanf("%lld",&n) == 1)
printf("%lld\n",g(n));
Java realization
import java.util.*;
public class
{
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));
}
}
}