Učenici na istim sedištima

Učenici gledaju dva filma u bioskopskoj sali u kojoj su sedišta raspoređena u \(m\) vrsta i \(n\) kolona (učenika ima tačno \(m\cdot n\)). Kada su gledali prvi film, nastavnici su ih rasporedili tako što su ih ređali po azbučnom redosledu popunjavajući vrstu po vrstu, a kada su gledali drugi film, ponovo su bili raspoređeni po azbučnom redosledu, ali ovaj put kolonu po kolonu. Napiši program koji određuje koliko učenika je sedelo na istom mestu tokom gledanja oba filma.

Opis ulaza

Sa standardnog ulaza se unose dva cela broja \(m\) i \(n\) (\(1 \leq m, n \leq 10000\)), svaki u posebnom redu.

Opis izlaza

Na standardni izlaz ispisati jedan ceo broj koji predstavlja broj učenika koji su tokom gledanja oba filma sedeli na istom sedištu.

Primer

Ulaz

Izlaz

Objašnjenje

Rešenje

Prilikom ređanja elemenata vrstu po vrstu pri čemu u jednoj vrsti ima \(n\) elemenata, element sa rednim brojem \(x\) nalazi u vrsti \(v_1 = x \,\mathrm{div}\,n\) i koloni \(k_1 = x\,\mathrm{mod}\,n\) (brojanje elemenata, vrsta i kolona počinje od nule). Dakle na osnovu definicije celobrojnog deljenja važi da je \(x = v_1\cdot n + k_1\), \(0 \leq k_1 < n\). Slično, ako se elementi ređaju kolonu po kolonu, i ako u jednoj koloni ima \(m\) elemenata, tada se element sa rednim brojem \(x\) nalazi u koloni \(k_2 = x\,\mathrm{div}\,m\) i vrsti \(v_2 = x\,\mathrm{mod}\,m\). Dakle, važi da je \(x = k_2 \cdot m + v_2\) i \(0 \leq v_2 < m\).

Da bi element bio na istoj poziciji mora da važi da je \(k_1 = k_2\) i da je \(v_1 = v_2\). Jedno direktno rešenje je da se za svaki redni broj učenika od \(0\) do \(m\cdot n - 1\) odrede \(v_1\), \(k_1\), \(v_2\) i \(k_2\) (celobrojnim deljenjem, na gore opisani način) i zatim da se vidi koliko tako određenih brojeva zadovoljava traženi uslov (rešenje se, dakle, zasniva na brojanju elemenata filtrirane serije).

using System;

class Program
{
    static void Main()
    {
        int m = int.Parse(Console.ReadLine());
        int n = int.Parse(Console.ReadLine());
        int brojNaIstimSedistima = 0;
        for (int ucenik = 0; ucenik < m*n; ucenik++)
        {
            int v1 = ucenik / m, k1 = ucenik % m;
            int k2 = ucenik / n, v2 = ucenik % n;
            if (v1 == v2 && k1 == k2)
                brojNaIstimSedistima++;
        }
        Console.WriteLine(brojNaIstimSedistima);
    }
}

Međutim, postoji i efikasnije rešenje. Na osnovu gore rečenog, mora da važi da je \(x = v_1 \cdot n + k_1 = k_2 \cdot m + v_2\), a pošto \(x\) zadovoljava uslov zadatka ako i samo ako važi \(k_1 = k_2\) i \(v_1 = v_2\), važi da je \(v_1 \cdot n + k_1 = k_1 \cdot m + v_1\), tj. \(v_1 \cdot (n - 1) = k_1 \cdot (m - 1)\). Pri tom, mora da važi da je \(0 \leq v_1 < m\) i \(0 \leq k_1 < n\). Rešenja ima onoliko koliko postoji parova \((v_1, k_1)\) koji zadovoljavaju dati uslov (takvi su sigurno parovi \((0, 0)\) i \((m-1, n-1)\), ali ih ima možda još. Označimo sa \(d\) najveći zajednički delilac brojeva \(n-1\) i \(m-1\). Neka je \(n-1 = s \cdot d\) i \(m-1 = t \cdot d\). Tada mora da važi \(v_1 \cdot s \cdot d = k_1 \cdot t \cdot d\), tj. \(v_1 \cdot s = k_1 \cdot t\), pri čemu su \(s\) i \(t\) uzajamno prosti brojevi. Ova jednačina je zadovoljena ako i samo ako postoji neko \(i\) takvo da je \(v_1 = i \cdot t\) i \(k_1 = i \cdot s\). Iz uslova da je \(0 \leq v_1 < m\) sledi da je \(0 \leq v_1 \leq m-1 = t\cdot d\), što znači da je neophodno da važi da je \(0 \leq i \leq d\). Slično, iz \(0 \leq k_1 < n\) sledi da je \(0 \leq k_1 \leq n-1 = s\cdot d\), što je opet ekvivalentno sa \(0 \leq i \leq d\). Dakle, parova \((v_1, k_1)\) koji zadovoljavaju \(v_1 \cdot (n - 1) = k_1 \cdot (m - 1)\), \(0 \leq v_1 < m\) i \(0 \leq k_1 < n\) jednak je broju vrednosti \(i\) koje zadovoljavaju \(0 \leq i \leq d\), a to je tačno \(d + 1\). Dakle, zadatak se može rešiti tako što se izračuna NZD brojeva \(m-1\) i \(n-1\) i taj NZD se uveća za jedan. NZD se može izračunati Euklidovim algoritmom. Različite varijante Euklidovog algoritma opisane su u zadatku [euklid].

using System;

class Program
{
    static int nzd(int a, int b)
    {
        while (b != 0)
        {
            int tmp = a % b;
            a = b;
            b = tmp;
        }
        return a;
    }

    
    static void Main()
    {
        int m = int.Parse(Console.ReadLine());
        int n = int.Parse(Console.ReadLine());
        
        Console.WriteLine(nzd(m-1, n-1) + 1);
    }
}

#include <iostream>

using namespace std;

int main() {
  int m, n;
  cin >> m >> n;
  int brojNaIstimSedistima = 0;
  for (int ucenik = 0; ucenik < m*n; ucenik++) {
    int v1 = ucenik / m, k1 = ucenik % m;
    int k2 = ucenik / n, v2 = ucenik % n;
    if (v1 == v2 && k1 == k2)
      brojNaIstimSedistima++;
  }
  cout << brojNaIstimSedistima << endl;
  return 0;
}

#include <iostream>

using namespace std;

int nzd(int a, int b) {
  while (b != 0) {
    int tmp = a % b;
    a = b;
    b = tmp;
  }
  return a;
}

int main() {
  int m, n;
  cin >> m >> n;
  cout << nzd(m-1, n-1) + 1 << endl;
  return 0;
}