Приближается Новый год! Третьеклассники уже мечтают побывать возле новогодней елки в Киеве. Учительница математики одного из 3-х классов г. Александрия им сообщила, что она сможет свозить на ёлку в Киев только тех учеников, которые решать задачку от святого Николая. Он хочет узнать качество заданного числа.
По мнению Николая, качеством числа [latex]N[/latex] является сумма цифр всех натуральных чисел [latex] A[/latex] не больших самого числа [latex] N[/latex] таких что остаток от деления числа [latex] N[/latex] на число [latex] A[/latex] равен [latex] 0[/latex] .
Входные данные
Первая строка содержит натуральное число [latex]N[/latex] – количество учеников в 3-м классе. В последующих [latex]N[/latex] строках размещены задания для каждого ученика: натуральное число не больше чем [latex] 15 000 000[/latex] (Николай решил пожалеть учеников и числа выбрал не очень большие)
Выходные данные
Для каждого из чисел, заданных Николаем ученикам, укажите его качество.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <iostream> #include <cmath> using namespace std; int SumOfDigit(int n) { int f = 0; while (n >= 1) { f += n % 10; n /= 10; } return f; } int main() { int N; cin >> N; for (int i = 1; i <= N; i++) { int A; cin >> A; int sum = 0; double f = sqrt(A); for (int j = 1; j*1.0 <= f; j++) { if (A%j == 0) sum += SumOfDigit(j) + SumOfDigit(A/j); } if ((int) f == f) sum-=f; cout<<sum<<endl; } return 0; } |
| Количество строк | 1 задание | 2 задание | Вывод |
| 2 | 2 | 10 | 3; 9 |
| 2 | 2 | 1500000 | 3; 666 |
| 2 | 5 | 9 | 6; 13 |
| 2 | 60 | 15000000 | 42; 978 |
| 2 | 1 | 0 | 1; 0 |
Решение
В данной задаче я выделил отдельную функцию — [latex]SumOfDigit()[/latex]. Не трудно догадаться, что она считает сумму цифр числа для будущих вычислений. Для первого цикла мы сначала должны ввести число [latex]N[/latex] — количество заданий для учеников. Именно столько раз будет выполняться основной цикл. Чтобы определить качество числа, необходимо найти все его натуральные делители. Для решения данной задачи я воспользовался методом перебора всех чисел до корня из исходного, что значительно ускоряет вычисление по сравнению с перебором вплоть до самого числа. Во внутреннем цикле проверяется каждое число, и если оно удовлетворяет условию, то вызывается функция [latex]SumOfDigit[/latex], а в переменную [latex]sum[/latex] записываются значения сумм.
|
1 |
if ((int) f == f) sum-=f; |
Данная строка необходима для проверки, если исходное число является квадратом.
В конце основного цикла программа печатает на экран качество данного числа.
Данная задача решалась совместно со Стасом Коциевским на факультативе.
Хорошо, но нужны ссылки на задачу, код и принятое решение (e-olymp.com, ideone.com).
Кроме того желательно использовать latex для математических символов и формул.
С ключевыми словами Вы так и не разобрались — удалил все кроме одного. Подойдите ко мне на занятии я объясню ещё раз.
Добавил ссылки и latex.
Я бы не пользовался в цикле дабловскими сравнениями. Они ненадежны — сегодня они верны, а завтра предадут. Есть несколько вариантов идти до корня числа:
1) int f = sqrt(A) + 0.5; …
2) for(int i = 1; i * i <= A; ++i) …
Еще, если бы это был серьезный проект, я бы вместо умножения на 1.0, использовал бы явное преобразование к даблу