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

Автор Coding_is_important, история, 4 года назад, По-английски

Is it good to solve Number Theory tagged problems on codeforces when I don't know Number Theory ?

Please give me some tips on how to be good on Number Theory.

Thanks.

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

»
4 года назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

Depending on your mathematical background and prowess, I recommend reading Arthur Engels Problem-Solving Strategies Chapter 6 .

It's primarily for mathematical competitions but I found it also very useful for programming — although maybe a bit overkill. It's a hard read, but worth it.

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

In my opinion, just try to solve it. I'm not that good at this kind of problems too, but if you keep trying to solve Number Theory problems, you will eventually gets better in the future. In codeforces, there are a lot of problems with Number Theory tags, and sometimes this kind of problem appears in contests, so practice solving this kind of problems really helps. So, just try to solve the easier problems first. (Sorry for my bad english).

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I guess you should because I've seen many problems on codeforces that use very basic NT concepts like GCD or something, but are still tagged with 'Number Theory'. But I think you should just go and learn number theory, you can probably learn a lot of it in 1 day, and for that, any Discrete Math book would be good.

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

it is good to try to solve any tagged problems of difficulty 800-1600 on codeforces even if you don't know anything about that tag

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I personally think that it is worth solving the problems of olympiad mathematics in number theory, since at the contest you have to display properties on a piece of paper and understand how it all works, as often happens in number theory. But don't think you need to have advanced knowledge. It is enough to solve problems on the properties of GCD, LCM, Fermat's theorem, decomposition into prime divisors, solution of an equation in integers. (I think these topics are the most frequently encountered), it seems to me that a week is enough to practice on a piece of paper with these topics so that I have enough skills to deduce and solve in competitions on sports programming

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You really don't need to know much number theory to solve most problems. The one harder technique you'll have to learn at some point is Mobius transform.