Problem Enumerating Rational Numbers

I don't know how to solve this problem, with the help of Euler's function. Can you explain me the idea for this problem?

Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

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

1 | MiFaFaOvO | 3681 |

2 | tourist | 3669 |

3 | Um_nik | 3535 |

4 | 300iq | 3317 |

5 | ecnerwala | 3294 |

6 | maroonrk | 3268 |

7 | TLE | 3223 |

8 | scott_wu | 3209 |

9 | WZYYN | 3180 |

10 | boboniu | 3174 |

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

1 | Errichto | 197 |

2 | antontrygubO_o | 185 |

3 | pikmike | 183 |

4 | Ashishgup | 182 |

5 | vovuh | 179 |

6 | Radewoosh | 173 |

7 | SecondThread | 167 |

8 | Um_nik | 164 |

9 | Monogon | 163 |

10 | McDic | 162 |

Problem Enumerating Rational Numbers

I don't know how to solve this problem, with the help of Euler's function. Can you explain me the idea for this problem?

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/12/2020 00:00:16 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Ok, got accepted.

http://pastebin.com/2rFPsEHx

Ah, you cant calc euler function for 1...n on each test case, too expensive(n * sqrt(n)), precalc it :)

nin time, using this approach:Wow, thnks for that. But it seems like the complexity is O(n*log(log(n)))

Wow. That is a clever use of the Divisor Sum property of the Euler Totient Function.

I know this is an old comment haha, but shouldn't

`phi[1] = 1`

? Since gcd(0, 1) = 1?Yes. You should initialize $$$\phi(1)=1$$$ and start the bottom loop from $$$i = 2$$$.