Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Mohab_Yaser's blog

Are Number Theory Advanced Topics Worth Learning in the Early Stages?
By Mohab_Yaser, history, 14 months ago, In English

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?

  • Vote: I like it
  • -12
  • Vote: I do not like it

»
14 months ago, # |
  Vote: I like it +42 Vote: I do not like it

I don't know any of them

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Chinese remainder theorem was useful

    → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      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)

      → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In a Div2 C, solution was based on CRT.

      → Reply
      • »
        »
        »
        »
        14 months ago, # ^ |
        ← Rev. 4   Vote: I like it +17 Vote: I do not like it

        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

        → Reply
»
14 months ago, # |
  Vote: I like it +12 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
14 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I dont know any of them

→ Reply
»
14 months ago, # |
  Vote: I like it +4 Vote: I do not like it

  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).

→ Reply