When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Coding_is_important's blog

By Coding_is_important, history, 3 years ago, In English

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.

| Write comment?
»
3 years ago, # |
  Vote: I like it +27 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.