Задача
Иван Петрович преподает в школе физкультуру, но интересуется также математикой, в основном, с практической точки зрения. Например, его интересует вопрос, сколько различных построений существует для группы из [latex]N[/latex] человек. Иван Петрович выяснил, что если [latex]N[/latex]– простое число, то получается только [latex]2[/latex] построения: в колонну по одному ([latex]1[/latex]×[latex]N[/latex]) и в шеренгу ([latex]N×1[/latex]). Эти тривиальные построения возможны для любого [latex]N[/latex] > [latex]1[/latex] (для [latex]N = 1[/latex] существует только одно построение ([latex]1×1[/latex]), которое не является ни шеренгой, ни колонной). Если [latex]N[/latex] – составное число, то существует и другие нетривиальные построения. Для [latex]100[/latex] человек существует девять построений: ([latex]1×100[/latex]), ([latex]2×50[/latex]), ([latex]4×25[/latex]), ([latex]5×20[/latex]), ([latex]10×10[/latex]), ([latex]20×5[/latex]), ([latex]25×4[/latex]), ([latex]50×2[/latex]) и ([latex]100×1[/latex]).
Входные данные
В первой строке ввода содержится одно целое число [latex]N[/latex] (1 ≤[latex]N[/latex]≤ 109).
Выходные данные
Вывести одно целое число – количество различных построений для группы из [latex]N[/latex] человек.
Тесты
| # | Входные данные | Выходные данные |
|---|---|---|
| 1 | 100 | 9 |
| 2 | 1 | 1 |
| 3 | 6 | 4 |
| 4 | 999983 | 2 |
| 5 | 2 | 2 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> #include <cmath> using namespace std; int main () { int NumberOfPeople; cin >> NumberOfPeople; if(NumberOfPeople == 1){ cout << 1; return 0; } else { int deviders = 0; for(int i = 1; i < sqrt(NumberOfPeople);i++){ if(NumberOfPeople % i == 0) deviders++; // проверка на делимость } deviders *= 2; int Root = sqrt(NumberOfPeople); if(Root*Root == NumberOfPeople) deviders++; // проверка корня на делимость cout << deviders; } return 0; } |
Решение задачи
По условию задачи требуется найти все возможные построения. Это значит, что мы должны найти все возможные варианты разбиения числа на множители. Для этого можно обойтись перебором всех делителей числа от 1 до корня из этого числа, а затем умножить полученное значение на 2 так как для нас имеет значение порядок делителей. Если корень из числа есть делитель данного числа то увеличиваем счетчик на 1.
Ссылки
Ссылка на e-olymp
Ссылка на ideone
Зачел, но мне не нравится то, что Вы делаете с формулами. Вы разбиваете формулы чуть не по одному символу. Вместо того, чтобы использовать \times Вы вставляете крестики. Для этой работы сойдёт и так, но тенденция опасная — Вы не latex изучаете, а выкручиваетесь, чтобы его не изучать.