Can anyone provide an explanation for this problem!! I am not able to understand the basic idea.

# | User | Rating |
---|---|---|

1 | Benq | 3797 |

2 | tourist | 3723 |

3 | Radewoosh | 3720 |

4 | ecnerwala | 3579 |

5 | ksun48 | 3463 |

6 | Um_nik | 3457 |

7 | maroonrk | 3446 |

8 | jiangly | 3432 |

9 | Petr | 3370 |

10 | scott_wu | 3350 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 208 |

2 | awoo | 184 |

2 | rng_58 | 184 |

4 | Errichto | 182 |

5 | SecondThread | 177 |

6 | Radewoosh | 176 |

6 | maroonrk | 176 |

6 | -is-this-fft- | 176 |

9 | Um_nik | 173 |

10 | antontrygubO_o | 170 |

Can anyone provide an explanation for this problem!! I am not able to understand the basic idea.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/21/2021 15:13:32 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

it simply search the result based on formula, for example, for n = 2

the result = 2/gcd(1,2) + 2/gcd(2,2) = 2 + 1 = 3

It is a naive approach and will time out.Please re-read the constraints and answer accordingly.

the sum =

where d is a divisor of n and φ(

x) is euler's totient function ... I don't have a proof for it ,I thought it was symmetric to which is equal to (from oeis) and it workedyou can precompute φ in O(n log n) after sieve

and you can generate all divisors of a number in O(number of divisors) using the information generated by sieve

then you can evaluate this sum in O(number of divisors) ... I don't know if that is enough to pass the TL .. because when I solved this problem I reduced the above sum into a function of the the prime factorization and hence I could evaluate it in O(log x) for any x

The main claim is that the sum is .

This can be proved easily since there are exactly numbers with and

i≤n.Now, since

dφ (d) is a multiplicative function, so isf(n).Therefore, we can calculate

ffor prime powers and multiply the results to getf(n).It turns out — that .

Now, preprocessing the Eratosthenes's Sieve in , we can now perform prime factorization in . It is easy to calculate

fonce we have the prime factorization.Therefore, the time complexity is which is good enough to pass.

I solved it using Pillai's Arithmetic Formula.

Since

gcd(i,N)1 < =i< =Nis one of the divisors ofNhence in order to compute the summation we need to find the sum . Now we need to findfreq(d) .We need to find the number ofi'ssuch thatgcd(i,N) =dhencei=d*jwhen you substitute this in the previous equation you'll get thisgcd(j,N/d) = 1 . This equation means that we need to find the number of numbers less thanN/dthat are coprime withN/d. This is called Euler's totient function.That is how you get this equationNow coming to the codechef problem , the only change that you need to make is to substitute

dwithN/d. Hence the sum now becomes which same as writingTry solving now.

i implemented what Noureldin and bhishma are talking about but i am getting TLE. here is my code what i did found totient[i] — n loglogn compute ans[i] — that too is n loglogn