Цікавий добуток (Розбір)

Оголосимо структуру даних map<int, int> m, яка буде підраховувати, скільки разів зустрічається добуток i \cdot j. Кількість унікальних добутків дорівнює розмірові відображення $m$.

Приклад

Розгляньмо другий приклад. Запишемо таблицю множення для матриці [2; 4] \times [2; 5].

Таблиця містить $9$ різних значень.

Реалізація алгоритму

Оголосимо структуру для зберігання даних.

map<int, int> m;

Читаємо вхідні дані.

scanf("%d %d %d %d",&a,&b,&c,&d);

Поміняємо місцями $a$ і $b$, а також $c$ і $d$, щоб виконувалися умови a \le b, c \le d.

if (a > b) swap(a,b);
if (c > d) swap(c,d);

Перебираємо всі можливі добутки i \cdot j. Для кожного добутку збільшуємо на $1$ значення, пов'язане з ключем i \cdot j у відображенні.

for(i = a; i <= b; i++)
for(j = c; j <= d; j++) 
  m[i*j]++;

Виводимо відповідь — розмір відображення $m$.

printf("%d\n",m.size());

Java реалізація

import java.util.*;

public class Main
{
  public static void main(String[] args) 
  {
    Scanner con = new Scanner(System.in);

Читаємо вхідні дані.

    int a = con.nextInt();
    int b = con.nextInt();
    int c = con.nextInt();
    int d = con.nextInt();

Поміняємо місцями $a$ и $b$, а також $c$ и $d$, щоб виконувалися умови a \le b, c \le d.

    if (a > b) {int temp = a; a = b; b = temp;}
    if (c > d) {int temp = c; c = d; d = temp;}

Оголосимо структуру для зберігання даних.

    Map<Integer,Integer> m = new HashMap<Integer,Integer>();

Перебираємо всі можливі добутки i \cdot j.

    for(int i = a; i <= b; i++)
    for(int j = c; j <= d; j++)
    {
      int key = i * j;

Збільшуємо на $1$ значення, пов'язане з ключем i \cdot j. Якщо з ключем $key$ значення ще не пов'язане, то за замовчуванням беремо його рівним $0$.

      m.put(key, m.getOrDefault(key, 0) + 1);
    }

Виводимо відповідь — розмір відображення $m$.

    System.out.println(m.size());
    con.close();
  }
}

Python реалізація

Читаємо вхідні дані.

a, b, c, d = map(int, input().split())

Оголосимо словник для зберігання даних.

m = {}

Поміняємо місцями $a$ и $b$, а також $c$ и $d$, щоб виконувалися умови a \le b, c \le d.

if a > b:
  a, b = b, a
if c > d:
  c, d = d, c

Перебираємо всі можливі добутки i \cdot j. Для кожного добутку збільшуємо на $1$ значення, пов'язане з ключем i \cdot j у словнику.

for i in range(a, b+1):
  for j in range(c, d+1):
    key = i * j
    m[key] = m.get(key, 0) + 1

Виводимо відповідь — розмір словника $m$.

print(len(m))