About this paper

Appears in:
Pages: 933-936
Publication year: 2016
ISBN: 978-84-608-8860-4
ISSN: 2340-1117
doi: 10.21125/edulearn.2016.1188

Conference name: 8th International Conference on Education and New Learning Technologies
Dates: 4-6 July, 2016
Location: Barcelona, Spain

PROBLEMS OF NUMBER THEORY IN PROGRAMMING CONTESTS

M. Falileeva, L. Shakirova, M. Kinder

Kazan Federal University (RUSSIAN FEDERATION)
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.
@InProceedings{FALILEEVA2016PRO,
author = {Falileeva, M. and Shakirova, L. and Kinder, M.},
title = {PROBLEMS OF NUMBER THEORY IN PROGRAMMING CONTESTS},
series = {8th International Conference on Education and New Learning Technologies},
booktitle = {EDULEARN16 Proceedings},
isbn = {978-84-608-8860-4},
issn = {2340-1117},
doi = {10.21125/edulearn.2016.1188},
url = {http://dx.doi.org/10.21125/edulearn.2016.1188},
publisher = {IATED},
location = {Barcelona, Spain},
month = {4-6 July, 2016},
year = {2016},
pages = {933-936}}
TY - CONF
AU - M. Falileeva AU - L. Shakirova AU - M. Kinder
TI - PROBLEMS OF NUMBER THEORY IN PROGRAMMING CONTESTS
SN - 978-84-608-8860-4/2340-1117
DO - 10.21125/edulearn.2016.1188
PY - 2016
Y1 - 4-6 July, 2016
CI - Barcelona, Spain
JO - 8th International Conference on Education and New Learning Technologies
JA - EDULEARN16 Proceedings
SP - 933
EP - 936
ER -
M. Falileeva, L. Shakirova, M. Kinder (2016) PROBLEMS OF NUMBER THEORY IN PROGRAMMING CONTESTS, EDULEARN16 Proceedings, pp. 933-936.
User:
Pass: