### lani1akea's blog

By lani1akea, history, 6 weeks ago, ,

Hello! I have a question. Find the sum of greater odd divisors of 1 to n. n <= 10^9 . For example: n == 7 and f(n) = greater odd divisor of n f(1) = 1 , f(2) = 1 , f(3) = 3 , f(4) = 1 , f(5) = 5 , f(6) = 3 , f(7) = 7 and answer is 21

•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 It's completely different problem, isn't it? Let's denote sum[x] as the sum of greater odd divisors of all numbers from 1 to x and gr[x] as the greater odd divisor of number x. If x is odd then gr[x] = x, if x is even then gr[x] = gr[x/2]. So we can divide our sum[n] on two parts, i.e. even and odd parts: $sum[n] = \sum_{i=1}^{n} gr[i] = \sum_{i=1,odd}^{n} i + \sum_{i=2,even}^{n} gr[i] =$ $(\frac{n+1}{2})^2 + sum[n/2]$We have simple recursion here. Code#include long long sum( int n ) { if( n == 0 ) return 0; long long m = (n+1) / 2; return sum(n/2) + m * m; } int main( void ) { int n; scanf( "%d", &n); printf( "%I64d\n", sum( n )); return 0; }