Death_Scythe's blog

By Death_Scythe, history, 2 months 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  

»
2 months ago, # |
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.

»
2 months ago, # |
  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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    What does "d" refer to in F(n), and could you please explain the proof for function F(n)?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please show how do you simplify the summation for particular p? Thanks!