Abstract:

There are many different competitions in the field of informatics with different objectives. In spite of these differences, they all share the same need for high quality tasks. This paper describes the algorithmic tasks of number theory of different levels of difficulty. Most tasks are used in the specific scope of teaching and learning informatics.

In this paper we consider the problems of enumerating the number of ordered tuples of positive inte-gers with fixed greatest common divisor and least common multiple, and we analyze the properties of the resulting arithmetic functions. The important feature of these tasks is that they are multilevel tasks. They assume to use solution algorithms of various complexity which depend on dimension of the task. All algorithms we present have low sample complexity that depends only on the input parameters.

Many of the examples in this paper are taken from the Open Cup named after E.V. Pankratiev (Grand-Prix of Tatarstan). Full texts for all of these problems are available on the Internet: http://codeforces.com/gym/100942?locale=en. We hope that some classes of such tasks would en-large scope of tasks for use in programming contests at various levels.

Keywords:

Programming contests, olympiads of informatics, tasks of number theory, training.