На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен). Необходимо определить количество пар, для которых произведение элементов делится на 26.
В первой строке входных данных задаётся количество чисел N(1 ≤ N ≤ 60 000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000. В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно 26.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N(1 ≤ N ≤ 60 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
Пример организации исходных данных во входном файле:
4
2
6
13
39
Пример выходных данных для приведённого выше примера входных данных:
4
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Ответ:
Пояснение. Из четырёх заданных чисел можно составить 6 попарных произведений: 2 · 6, 2 · 13, 2 · 39, 6 · 13, 6 · 39, 13 · 39 (результаты: 12, 26, 78, 78, 234, 507). Из них на 26 делятся 4 произведения (2 · 13 = 26; 2 · 39 = 78; 6 · 13 = 78; 6 · 39 = 234).
Решение. Произведение двух чисел делится на 26, если выполнено одно из следующих условий (условия не могут выполняться одновременно).
А. Оба сомножителя делятся на 26.
Б. Один из сомножителей делится на 26, а другой не делится.
В. Ни один из сомножителей не делится на 26, но один сомножитель делится на 2, а другой — на 13.
Примечание для проверяющего. Условие делимости произведения на 26 можно сформулировать проще, например так: (один из сомножителей делится на 26) ИЛИ (один сомножитель делится на 2, а другой — на 13). Но в этом случае пара сомножителей может удовлетворять обоим условиям, что затруднит подсчёт количества пар.
При вводе чисел можно определять, делится ли каждое из них на 26, 2 и 13, и подсчитывать следующие значения:
1) n26 — количество чисел, кратных 26;
2) n13 — количество чисел, кратных 13, но не кратных 26;
3) n2 — количество чисел, кратных 2, но не кратных 26.
Примечание для проверяющего. Сами числа при этом можно не хранить. Каждое число учитывается не более чем в одном из счётчиков. Количество пар, удовлетворяющих условию А, можно вычислить по формуле n26 · (n26 – 1) : 2.
Количество пар, удовлетворяющих условию Б, можно вычислить по формуле n26 · (N – n26).
Количество пар, удовлетворяющих условию В, можно вычислить по формуле n2 · n13.
Приведём решение Юрия Красильникова на языке Python.
#Решение на питоне, подсчет чисел с разной делимостью:
a=[int(s) for s in open('27989_B.txt')][1:]
m2=len([x for x in a if x%2==0 and x%13!=0])
m13=len([x for x in a if x%13==0 and x%2!=0])
m26=len([x for x in a if x%26==0])
m=len(a)
print(m26*(m26-1)//2 + m26*(m-m26) + m2*m13)
Приведём решение Юрия Красильникова на языке Python.
#Выбираем числа последовательности по очереди и прибавляем к счетчику пар число пар, которое очередное число образует с предыдущими:
a = [int(s) for s in open('27989_B.txt')][1:]
cnts = [0]*4
k = 0 # счетчик количества пар
for x in a:
n = (x%2==0)*2 + (x%13==0) # n=0 - не делится ни на 2, ни на 13.
# n=2 - делится на 2; n=1 - делится на 13; n=3 - делится на 26;
PDF-версии: 