Блог пользователя Death_Scythe

Hanumant and His Love — CodeBattle Problem
Автор Death_Scythe, история, 8 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +35
  • Проголосовать: не нравится

»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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

→ Ответить