e-olymp 8669. Все делители

Условие задачи

Найдите все делители натурального числа $n$.

Входные данные

Одно натуральное число $ n ( n \leqslant 10^9 ) $.

Выходные данные

Выведите в возрастающем порядке все делители числа $n$.

Тесты

Входные данные Выходные данные
1 10 1 2 5 10
2 36 1 2 3 4 6 9 12 18 36
3 455 1 5 7 13 35 65 91 455
4 38965 1 5 7793 38965
5 999999 1 3 7 9 11 13 21 27 33 37 39 63 77 91 99 111 117 143 189 231 259 273 297 333 351 407 429 481 693 777 819 999 1001 1221 1287 1443 2079 2331 2457 2849 3003 3367 3663 3861 4329 5291 6993 8547 9009 10101 10989 12987 15873 25641 27027 30303 37037 47619 76923 90909 111111 142857 333333 999999
6 1000000000 1 2 4 5 8 10 16 20 25 32 40 50 64 80 100 125 128 160 200 250 256 320 400 500 512 625 640 800 1000 1250 1280 1600 2000 2500 2560 3125 3200 4000 5000 6250 6400 8000 10000 12500 12800 15625 16000 20000 25000 31250 32000 40000 50000 62500 64000 78125 80000 100000 125000 156250 160000 200000 250000 312500 320000 390625 400000 500000 625000 781250 800000 1000000 1250000 1562500 1600000 1953125 2000000 2500000 3125000 3906250 4000000 5000000 6250000 7812500 8000000 10000000 12500000 15625000 20000000 25000000 31250000 40000000 50000000 62500000 100000000 125000000 200000000 250000000 500000000 1000000000

Код

Код №1

Код №2

Решение

Можно заметить, что делитель и частное взаимодополняют друг друга. Мы найдем делители, потом частные этого выражения. Так как частные также являются делителями. Значит последовательность делителей в порядке возрастания можно разделить на две части. Создадим два цикла для нахождения этих двух частей:

  1. В первом цикле проверяем каждое натуральное число от $1$ до $\sqrt n$. В коде №1 выводим числа, если они являются делителями. В коде №2 помещаем их в стек и выводим;
  2. Во втором цикле в коде №1 делим заданное число $n$ на все делители и выводим. В коде №2 делим заданное число $n$ на все элементы стека и выводим.

Примечание: для избежания повторения в коде №2, удаляем $\sqrt n$ из стека.

Ссылки

Условие задачи на E-olymp

Код №1 на Ideone

Код №2 на Ideone

Засчитанный код №1 на E-olymp

Засчитанный код №2 на E-olymp

e-olymp 4752.  Кинотеатр

Задача

Однажды, ученики B-й школы города G решили съездить в кино. Администрация кинотеатра расположила их в зале размера $n × m$, который специально был подобран так, чтобы все места были заняты школьниками. Каждому посетителю кинотеатра был выдан свой номер.

Школьники заняли свои места следующим образом: они входили в зал в порядке, в котором шли их номера, и полностью занимали сначала первый ряд, потом второй, потом третий и т.д.

Однако классный руководитель решил, что такая рассадка плохо влияет на поведение учащихся и пересадил их по-другому: ученики сначала занимали все первые места каждого ряда, потом все вторые места каждого ряда и т.д. (см. рисунок).

Администрация решила выяснить, сколько учащихся не поменяют своего места после пересадки.

Входные данные:
В первой строке заданы числа $n$ и $m$ $(1 \le n, \le 1000)$.

Выходные данные:
Выведите одно число — количество учеников, которые в результате пересадки останутся сидеть на тех же местах.

Тесты

Входные данные Вывод программы
3 3 3
3 2 2
231 543 3

Continue reading