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

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

1 | tourist | 3556 |

2 | wxhtxdy | 3520 |

3 | Radewoosh | 3409 |

4 | Benq | 3368 |

5 | mnbvmar | 3280 |

6 | ecnerwala | 3278 |

7 | LHiC | 3276 |

8 | sunset | 3264 |

9 | maroonrk | 3159 |

10 | TLE | 3145 |

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

1 | Errichto | 189 |

2 | Radewoosh | 177 |

3 | tourist | 173 |

4 | antontrygubO_o | 172 |

5 | Vovuh | 166 |

5 | PikMike | 166 |

7 | rng_58 | 157 |

8 | majk | 156 |

9 | farmersrice | 154 |

10 | Um_nik | 153 |

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

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2019 04:59:31 (h2).

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.