Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

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

Are Number Theory Advanced Topics Worth Learning in the Early Stages?
Автор Mohab_Yaser, история, 14 месяцев назад, По-английски

I studied some number theory basic topics and after that I found some topics in some Youtube playlists such as:

  • Euler totient
  • Möbius inversion
  • Chinese remainder theorem
  • Diophantine equation
  • Linear/segmented sieve
  • Miller Rabin primality testing
  • etc.

Are these topics really important and frequent in problems with rates $$$<1800$$$ and worth time or it's just a waste of time to learn them now?

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

»
14 месяцев назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

I don't know any of them

→ Ответить
  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Chinese remainder theorem was useful

    → Ответить
    • »
      »
      »
      14 месяцев назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

      I think that if solution of problem uses CTO(chinese remainder theorem), its have another solution. But i think only CTO and Diophantine equation are useful(especcialy for < 2000)

      → Ответить
    • »
      »
      »
      14 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      In a Div2 C, solution was based on CRT.

      → Ответить
      • »
        »
        »
        »
        14 месяцев назад, # ^ |
        ← Rev. 4   Проголосовать: нравится +17 Проголосовать: не нравится

        Exactly. 1770C KoxiaAndNumTheory Problem could be solved without CRT. The intuition is to check if there're duplicate elements or same remainder upon division by a prime. But CRT provides a rigorous proof to this intuition. (Check editorial)

        So I would suggest from these topics Linear/segmented sieve, CRT and Diophantine equations

        This easy but Diophantine equations read to have a deeper understanding of your solution is something good so still maybe Diophantine equations useful

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

You'll not see most of them in problems with <2500, maybe.

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

You should learn the fifth one. The other one? Nah they hurt my brain, there're no chance they will occur in $$$ < 1800 $$$ problems, or even $$$<2100$$$ problems.

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

You can learn Euler totient, Linear Sieve and Chinese remainder theorem. these will be helpful..

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

I dont know any of them

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

  1. Euler Totient is sometimes useful.

  2. I don't know what that is.

  3. Really annoying thing to implement that never appears below d1C/d2E. Only useful if the author is unable to write a problem that's actually good.

  4. :weary:

  5. I've been doing CP for 7 years, and i've never needed more than the standard sieve

  6. Somewhat useful to know if it appears in onsite competitions, otherwise you should just know from where to copy it.

Problems on codeforces don't really have any advanced topics below 2500-2600 rating (or maybe even higher but I can't solve those).

→ Ответить