Задача к ЕГЭ по информатике на тему «количество информации и комбинаторика» №2

Просмотров 8 Комментарии 0

Сколькими способами можно представить $1125$ в виде произведения трёх множителей, если произведения, отличающиеся порядком множителей, считаются одинаковыми? (например, $1⋅1 ⋅1125$ и $1125⋅1 ⋅1$ — один вариант)

Решение неэффективно:

ans = [[1, 1, 1125]]
for i in range(1, 1125 // 2):
    for j in range(i, 1125 // 2):
        for k in range(j, 1125 // 2):
            if i * j * k == 1125:
                ans.append([i, j, k])
print(len(ans))

Решение эффективно:

a = []
for i in range(2+1):
    for j in range(3+1):
        a.append(3**i * 5**j)

ans = []

# Три множителя различны
for i in range(len(a)):
    for j in range(i+1, len(a)):
        for k in range(j+1, len(a)):
            if a[i]*a[j]*a[k] == 1125:
                ans.append((a[i], a[j], a[k]))

# Два множителя одинаковы, третий другой
for i in range(len(a)):
    for j in range(i+1, len(a)):
        if a[i]**2 * a[j] == 1125:
            ans.append((a[i], a[i], a[j]))
        if a[i] * a[j]**2 == 1125:
            ans.append((a[i], a[j], a[j]))

# Все три множителя одинаковы
for i in range(len(a)):
    if a[i]**3 == 1125:
        ans.append((a[i], a[i], a[i]))

print(len(ans))

Ответ: 12