Se una tabella di moltiplicazione NxM viene ordinata, qual è il numero nel mezzo?

Question

se ho una tabella di moltiplicazione di dimensioni, ad esempio, 3x5:

1 2 3 4 5 
2 4 6 8 10 
3 6 9 12 15 

e ho messo tutti questi numeri in ordine:

1 2 2 3 3 4 4 5 6 6 8 9 10 12 15 

Qual è il numero in mezzo? In questo caso, è 5.

N e M sono sempre dispari, quindi può esserci una sola risposta.

Esiste una soluzione rapida per questo? Sto cercando qualcosa tra le righe di O(N log NM)

Questo è un tipo di compiti a casa, ma sono davvero perso con questo. Mi è venuta in mente alcune idee, ma tutti avevano alcune carenze:

public class Table { 

    public static void main(String[] ar) { 
     Scanner scanner = new Scanner(System.in); 
     int w = scanner.nextInt(); 
     int h = scanner.nextInt(); 

     int[] s = new int[w * h + 1]; 
     for (int i = 1; i <= w; i++) 
      for (int j = 1; j <= h; j++) 
       s[i * j] = s[i * j] + 1; 

     int sum = 0; 
     for (int i = 0; i < s.length; i++) { 
      sum += s[i]; 
      if (sum >= s.length/2) { 
       System.out.println(i); 
       break; 
      } 
     } 
    } 

} 

Questo risolve la maggior parte dei test abbastanza veloce (< 4S), ma per la grande N e M, i limiti di memoria sono superati (I non conosciamo le limitazioni esatte).

L'idea è di tenere traccia delle occorrenze di ogni numero e quindi scorrere tutti i numeri in ordine, aggiungendo il numero di occorrenze ciascuna iterazione. Quando il numero di occorrenze è superiore o uguale a w * h/2, è il numero nel mezzo e lo stampiamo.

public class Table { 

    public static void main(String[] ar) { 
     Scanner scanner = new Scanner(System.in); 
     int w = scanner.nextInt(); 
     int h = scanner.nextInt(); 

     int sum = 0; 
     for (int i = 1; i <= w * h; i++) { 
      for (int j = 1; j <= Math.sqrt(i); j++) { 
       if (i % j == 0) { 
        int k = i/j; 
        if (k <= w && k != j) sum++; 
        if (k <= h && k != j) sum++; 
        if (k <= w && k <= h && k == j) sum++; 
       }     
      } 

      if (sum >= (w * h + 1)/2) { 
       System.out.println(i); 
       break; 
      } 
     } 
    } 

} 

tentativo di superare i limiti di memoria, ho provato a contare le occorrenze di ogni numero fino a quello centrale come vengono. Ho notato che il numero di occorrenze in una tabella di moltiplicazione di ciascun numero è il numero di fattori che hanno.

Non abbastanza veloce.

---

Qualcuno può venire con qualsiasi suggerimento? So che nella ricerca suggerita O(N log NM) viene utilizzata la ricerca binaria.

---

1 <= N <= 10^5 
1 <= M <= 10^5 

---

soluzione!

Ok, quindi grazie a @PeterdeRivaz sono riuscito a trovare e implementare una soluzione per il mio problema. L'idea è come la descrive, e qui è la realizzazione effettiva:

 
    public class Kertotaulu { 

 
     public static void main(String[] ar) { 
      Scanner scanner = new Scanner(System.in); 
      long h = scanner.nextLong(); 
      long w = scanner.nextLong(); 

 
      long min = 1; 
      long max = w*h; 
      long mid = 0; 
      while (min <= max) { 
       mid = (min + max)/2; 
       long sum = 0; 
       for (int i = 1; i <= h; i++) sum += Math.min(mid/i, w); 
       sum--; 

 
       if (sum < (w * h)/2) min = mid + 1; 
       else if (sum > (w * h)/2) max = mid - 1; 
       else break; 
      } 

 
      long sum = 0; 
      for (int i = 1; i <= h; i++) sum += Math.min((mid - 1)/i, w); 
      sum--; 

 
      if (sum == (w * h)/2) System.out.println(mid - 1); 
      else System.out.println(mid); 
     } 

 
    }

Answer 1

È possibile usare la ricerca binaria sul valore contando quante voci nella moltiplicazione la tabella sarà inferiore al valore.

Ciò richiederà iterazioni log (NM) nella ricerca binaria, quindi dobbiamo essere in grado di calcolare il conteggio in O (N) per una complessità totale di O (Nlog (NM)).

Questo può essere fatto considerando ciascuna tabella di moltiplicazione a turno. Ad esempio, supponiamo che il nostro valore di prova sia 8 e stiamo considerando la tabella 3 volte.

I valori inferiori a otto saranno 3 * 1 e 3 * 2. Possiamo trovare quante sono semplicemente dividendo il valore di test 8 dalla tabella 3 e arrotondando per difetto, cioè floor (8/3) = 2 quindi la tabella 3 volte ci darà un conteggio di 2.