На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре неважен). Необходимо определить количество пар, для которых произведение элементов кратно 62.
В первой строке входных данных задаётся количество чисел N(1 ≤ N ≤ 60 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000. В качестве результата программа должна вывести одно число: количество пар, в которых произведение элементов кратно 62.
Пример организации исходных данных во входном файле:
5
2
6
13
31
93
Пример выходных данных для приведённого выше примера входных данных:
4
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Ответ:
Пояснение. Из 5 чисел можно составить 4 пары, удовлетворяющие условию. Для заданного набора чисел получаем пары (2, 31),(2, 93),(6, 31),(6, 93).
Решение. Произведение двух чисел делится на 62, если выполнено одно из следующих условий (условия не могут выполняться одновременно).
А. Оба сомножителя делятся на 62.
Б. Один из сомножителей делится на 62, а другой не делится.
В. Ни один из сомножителей не делится на 62, но один сомножитель делится на 2, а другой — на 31.
При вводе чисел можно определять, делится ли каждое из них на 62, 2 и 31, и подсчитывать следующие значения:
1) n62 — количество чисел, кратных 62;
2) n31 — количество чисел, кратных 31, но не кратных 62;
3) n2 — количество чисел, кратных 2, но не кратных 62.
Количество пар, удовлетворяющих условию А, можно вычислить по формуле n62 · (n62 – 1) : 2.
Количество пар, удовлетворяющих условию Б, можно вычислить по формуле n62 · (N – n62).
Количество пар, удовлетворяющих условию В, можно вычислить по формуле n2 · n31.
PDF-версии: 