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:
![](https://espresso.codeforces.com/21d6547687c461cf8015d303db965f02a1410a42.png)
where p is a prime and φ(m) is the Euler totient function.
Thanks!
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
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!
Name |
---|
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.
Use the following identity:
For a particular p it turns out the summation is of the form:
where
What does "d" refer to in F(n), and could you please explain the proof for function F(n)?
Can you please show how do you simplify the summation for particular p? Thanks!