На вход программы поступает последовательность из 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;
На вход программы поступает последовательность из 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.
