Interesting Product (Editorial)

Declare a data structure map<int, int> m to count how many times the product i \cdot j occurs. The number of unique products is equal to the size of the map $m$.

Example

Let's consider the second example. Let's write the multiplication table for the matrix [2; 4] \times [2; 5].

The table contains $9$ unique values.

Algorithm implementation

Declare a structure for storing data.

map<int, int> m;

Read the input data.

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

Swap $a$ and $b$, as well as $c$ and $d$, to ensure the conditions a \le b, c \le d are satisfied.

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

Iterate through all possible products i \cdot j. For each product, increment by $1$ the value associated with the key i \cdot j in the map.

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

Print the result — the size of the map $m$.

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

Java implementation

import java.util.*;

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

Read the input data.

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

Swap $a$ and $b$, as well as $c$ and $d$, to ensure the conditions a \le b, c \le d are satisfied.

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

Declare a structure for storing data.

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

Iterate through all possible products i \cdot j.

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

Increment by $1$ the value associated with the key i \cdot j. If no value is associated with the key yet, default it to $0$.

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

Print the result — the size of the map $m$.

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

Python implementation

Read the input data.

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

Declare a dictionary for storing data.

m = {}

Swap $a$ and $b$, as well as $c$ and $d$, to ensure the conditions a \le b, c \le d are satisfied.

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

Iterate through all possible products i \cdot j. For each product, increment by $1$ the value associated with the key i \cdot j in the dictionary.

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

Print the result — the size of the dictionary $m$.

print(len(m))