Death_Scythe's blog

Hanumant and His Love — CodeBattle Problem
By Death_Scythe, history, 7 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

»
7 years 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.

→ Reply
»
7 years 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

→ Reply
  • »
    »
    7 years 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)?

    → Reply
  • »
    »
    7 years 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!

    → Reply