Death_Scythe's blog

Hanumant and His Love — CodeBattle Problem
By Death_Scythe, history, 9 years ago, In English

Hi!

How to solve the following problem: https://www.hackerearth.com/problem/algorithm/hanumant-and-his-love/description/

The problem asks to solve the following summation:

where p is a prime and φ(m) is the Euler totient function.

Thanks!

  • Vote: I like it
  • +35
  • Vote: I do not like it

»
9 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

This can help you: φ(x) is multiplicative function so, φ(pj) = φ(p) * φ(j) = (p - 1) * φ(j)

I'm not sure about solution, but I think this will be used in solution.

→ Reply
»
9 years ago, hide # |
 
Vote: I like it +20 Vote: I do not like it

Use the following identity:

For a particular p it turns out the summation is of the form:

(p - 1) * F(n) + (p - 1) * F(⌊ n / p⌋) + (p - 1) * F(⌊ n / p2⌋) + .....

where

→ Reply