Hal yang sangat dasar dalam Competitive Programming adalah Modulo Arithmetic, hal ini sangat penting diketahui dalam OSP maupun OSN, jadi sekarang saya akan membahasnya disini.
Karena tidak jarang peserta yang sudah sampai ke OSN pun masih belum mengerti bagaimana cara kerja Modulo Arithmetic ini.

Level	Basic
Type	Math
Requirement
Similar

Modulo

Pertama - tama kita kenalan dulu dengan modulo, biasanya di Pascal menggunakan operasi 'mod' sedangkan di C++ menggunakan operasi '%'.

Apakah gunanya?
Misalkan a % b = c, penjelasan simpelnya adalah, sisa bagi a dibagi b adalah c.
Misalkan 11 % 3 = 2, karena obvius sisa bagi 11 dibagi 3 adalah 2.
Dan maksud modulo ini bisa dilambangkan dengan cara lain yaitu 11 = 3*3 + 2.

Ya intinya kira - kira begitu. Simpel enough kan?

Tapi di matematika murni atau apalah *kurang ngerti juga, modulo itu dimaksudkan untuk kongruensi *atau apalah, I'm not really expert at this, so cmiiw.

Misalkan contoh diatas itu biasanya ditulis 11 ≡ 2 (mod 3).
Perlu di note itu bukan tanda sama dengan, tapi tanda kongruen.

Nah apakah maksud notasi di atas? itu artinya 11 itu kongruen dengan 2, jika modnya itu 3. *atau something like that lah, I'm not expert.
Jadi misalkan saya tulis 11 = 5 (mod 3) juga valid, karena 11 mod 3 sama dengan 5 mod 3. Artinya 11 juga kongruen dengan 5 jika di mod 3. Sudah sampai sini saja, saya tidak bisa menjelaskan lebih *duh.

Penggunaan Modulo

Dan mungkin anda bertanya - tanya modulo itu dipakai untuk apa sih?
Jawaban obviousnya adalah mencari sisa bagi.
Terus sisa baginya untuk apaan?
Jadi bisa berbagai jawaban sih sebenarnya.

Ganjil atau Genap

Fungsi modulo yang sering dipakai adalah untuk mencari tahu bahwa suatu bilangan ganjil atau genap. How?
Pertama - tama definisi bilangan ganjil adalah bilangan yang tidak habis dibagi dua atau bisa dikatakan jika dibagi dua, dia memiliki sisa, benarkan?
Sedangkan sebaliknya bilangan genap itu bilangan yang habis dibagi dua, atau bisa dikatakan tidak memiliki sisa.

Jadi untuk mengecek bilangan ganjil bisa dengan mudah dengan melakukan pengecekan seperti ini

if(bilangan % 2 == 1) // bilangan ganjil

Dan untuk bilangan genap

if(bilangan % 2 == 0) // bilangan genap

Begitu sederhana... :D

Waktu

Kegunaan yang lain bisa dibilang sangat obvious, seandainya anda memiliki N detik, anda diminta untuk mengubahnya menjadi bentuk jam, menit dan detik, dengan menit tidak boleh lebih dari angka 59, dan detik juga tidak boleh lebih dari angka 59, jadi disinilah digunakan mod.

detik = jumlah % 60; // mengambil detik keberapa sekarang
jumlah = jumlah / 60; // menjadikan jumlah tersebut menjadi menit
menit = jumlah % 60; // mengambil menit keberapa sekarang
jumlah = jumlah / 60; // menjadikan jumlah tersebut menjadi jam
jam = jumlah;

Cycle

Untuk cycle, apa ya maksudnya :-?... misalkan anda mempunyai counter untuk jumlah suatu tertentu, tetapi anda ingin jika dia lewat dari suatu bilangan, dia balik lagi menghitung dari awal. Tentu ini bisa dilakukan dengan mudah menggunakan if, tapi saya tunjukkan menggunakan modulo.

//di dalam suatu loop
  counter++;
  counter = counter % n;
//...

Misalnya anda ingin membuat queue yang siklik, anda bisa melakukan dengan cara ini untuk menentukan indeks mana yang ingin ditaruh dengan item sekarang.

Pengambilan Digit

Misalkan ada angka 124198, anda ingin mengetahui angka satuannya, bagaimana caranya?
Cara paling mudah adalah menggunakan modulo, 124198 % 10 = 8.
Untuk ratusan? Tinggal bagi dulu dengan 100 kemudian modulo 10, (124198 / 100) % 10 = 1241 % 10 = 1.

Hashing

Tidak terlalu penting untuk sekarang, tapi hashing itu bisa dibilang seperti ini. Hash map itu adalah tipe data mirip array, fungsinya untuk menaruh item, dan mencari apakah item tersebut ada di dalam data atau tidak dengan harapan kompleksitas O(1). Caranya adalah misalkan kita mempunyai suatu item, item tersebut akan diproses menjadi suatu key (indeks di array), kemudian taru item tersebut di indeks key pada array. Nah proses pengubahan dari item menjadi key ini disebut hash function (kalau tidak salah ingat), dan beberapa implementasinya menggunakan modulo.
Misalkan itemnya berupa integer, kita bisa dengan mengubah item tersebut menjadi key dengan cara integer tersebut lah yang menjadi key atau indeksnya.
Jadi misalkan itemnya 1212123, dia akan disimpen didalam indeks a[1212123]. Tetapi ini menjadi problem jika angkanya besar, sedangkan hanya ada beberapa item, kita menggunakan memori yang banyak sedangkan item yang ada hanya sedikit (banyak indeks array yang kosong). Sehingga digunakanlah modulo, misalkan kita modulo dengan 60, jadi kita hanya memerlukan 60 indeks untuk menyimpan, karena keynya pasti hanya dari 0 sampai 59 saja.
Dan karena ini akan sering terjadi collision, yaitu 2 item atau lebih yang berbeda mempunyai key yang sama, andaikata item 121 dengan item 61, jika sama - sama dimodulo 60, maka memiliki key 1. Itu yang disebut collision.
Biasanya Hash Map akan menghandle dengan membuat array lagi didalam indeks array hash, sehingga dapat menampung lebih dari satu item.
Jadi jika sudah diketahui keynya, dia akan mengiterasi array yang didalam indeks tersebut untuk mencari ada atau tidaknya.
Jadi bisa disimpulkan semakin sedikit collision semakin bagus, kita ingin meminimalkan jumlah item di dalam suatu indeks array, karena jika kita sudah mendapatkan keynya, tinggal O(1) saja pengecekannya.
Dan dari kata sesepuh dan dengar - dengar, katanya bilangan prima yang besar bisa memberikan harapan bahwa keynya bisa lebih tersebar, sehingga semakin sedikit collision yang terjadi.

Btw kenapa kita menjadi ngomongin hashing? It's not the main topic thought ==a... *Hashing mungkin akan dilanjutkan di post yang lain, yang ini hanya untuk diketahui doang kok, dan jarang digunakan di Competitive Programming, dan selama yang aku tahu, ini hanya dipakai di Pelatnas 2, pas belajar String Matching dengan algo Rabin-Karp, karena algo itu memerlukan hashing.

Operasi Modulo

Ini adalah bagian terpenting dari semuanya, karena ini digunakan di OSK, OSP maupun OSN.

Beberapa sifat modulo adalah...

(a + b) % md = (a % md + b % md) % md
(a - b) % md = (a % md - b % md) % md
(a * b) % md = (a % md * b % md) % md
(a ^ b) % md = ((a % md) ^ b) % md

Aku malas membuktikannya sehingga anda terima saja LOL...
Jika dilihat ini tidak berlaku untuk pembagian... as far as I know.

Penggunaan Operasi Modulo

Anda mungkin pernah lihat soal seperti ini...

(2^2012) % 7 = ?

Atau soal semacamnya, yang jika kita kerjakan manual tanpa trik bisa membuat tangan keriting.

Dengan mengeksploitasi sifat modulo diatas kita bisa mengerjakan seperti ini...
Menggunakan sifat perkalian, kita lakukan seperti ini, saya tidak akan menuliskan notasi matematika dengan benar, karena akan panjang jadi kita langsung main cepat...

(2 ^ 2012) % 7 =
= 2 * (2 ^ 2011) % 7
= 4 * (2 ^ 2010) % 7
= 1 * (2 ^ 2009) % 7 // (4*2)%7 = 1
= 2 * (2 ^ 2008) % 7
...
...

Dan anda akan memperoleh jawabannya setelah mengerjakan hal yang sama sebanyak 2012 kali.
Dan ini sama aja bunuh diri dalam kontes, karena ada cara yang lebih cepat.
Yaitu kita bisa membagi - bagi dalam menghitungnya, misalkan kita memecah 2012 itu menjadi 2, yaitu 2^1006 dan 2^1006, kemudian baru mengalikan hasilnya, itu jadi jauh lebih cepat, karena kita hanya perlu mengerjakan sebanyak 1006 kali dibandingkan 2012 kali (2 kali lebih cepat).

Dan hal selanjutnya adalah kita bisa membelah 2^1006 menjadi lebih kecil dan lebih kecil, sehingga kita bisa mengerjakan yang lebih kecil kemudian menggabungkannya.
Contoh pengerjaan seperti berikut

(2 ^ 2012) % 7 = ((2^1006 % 7) * (2^1006 % 7)) % 7
(2 ^ 1006) % 7 = ((2^503 % 7) * (2^503 % 7)) % 7
(2 ^ 503) % 7 = ((2^251 % 7) * (2^251 % 7) * 2) % 7
(2 ^ 251) % 7 = ((2^125 % 7) * (2^125 % 7) * 2) % 7
(2 ^ 125) % 7 = ((2^62 % 7) * (2^62 % 7) * 2) % 7
(2 ^ 62) % 7 = ((2^31 % 7) * (2^31 % 7)) % 7
(2 ^ 31) % 7 = ((2^15 % 7) * (2^15 % 7) * 2) % 7
(2 ^ 15) % 7 = ((2^7 % 7) * (2^7 % 7) * 2) % 7
(2 ^ 7) % 7 = ((2^3 % 7) * (2^3 % 7) * 2) % 7

(2 ^ 3) % 7 = 8 % 7 = 1

(2 ^ 7) % 7 = (1 * 1 * 2) % 7 = 2
(2 ^ 15) % 7 = (2 * 2 * 2) % 7 = 1
(2 ^ 31) % 7 = (1 * 1 * 2) % 7 = 2
(2 ^ 62) % 7 = (2 * 2) % 7 = 4
(2 ^ 125) % 7 = (4 * 4 * 2) % 7 = 4
(2 ^ 251) % 7 = (4 * 4 * 2) % 7 = 4
(2 ^ 503) % 7 = (4 * 4 * 2) % 7 = 4
(2 ^ 1006) % 7 = (4 * 4) % 7 = 2
(2 ^ 2012) % 7 = (2 * 2) % 7 = 4

Jadi jawabannya 4, walaupun lumayan panjang, setidaknya kita tidak perlu sampai 2012 kali menghitung LOL, ada cara lain yang cukup patut dicoba, yaitu dengan menghitung pangkat nya yang merupakan dua pangkat @.@, lihat contoh dibawah untuk lebih jelasnya.

(2 ^ 2012) % 7 = ((2^1024 % 7) * (2^988 % 7)) % 7
(2 ^ 988) % 7 = ((2^512 % 7) * (2^476 % 7)) % 7
(2 ^ 512) % 7 = ((2^256 % 7) * (2^220 % 7)) % 7
(2 ^ 220) % 7 = ((2^128 % 7) * (2^92 % 7)) % 7
(2 ^ 92) % 7 = ((2^64 % 7) * (2^28 % 7)) % 7
(2 ^ 28) % 7 = ((2^16 % 7) * (2^12 % 7)) % 7
(2 ^ 12) % 7 = ((2^8 % 7) * (2^4 % 7)) % 7

(2 ^ 2012) % 7 = (2 ^ (1024+512+256+128+64+16+8+4) ) % 7

(2 ^ 1) % 7 = 2
(2 ^ 2) % 7 = 4
(2 ^ 4) % 7 = 2
(2 ^ 8) % 7 = 4
(2 ^ 16) % 7 = 2
(2 ^ 32) % 7 = 4
(2 ^ 64) % 7 = 2
(2 ^ 128) % 7 = 4
(2 ^ 256) % 7 = 2
(2 ^ 512) % 7 = 4
(2 ^ 1024) % 7 = 2

(2 ^ 2012) % 7 = (2*4*2*4*2*2*4*2) % 7 = 4

Atau cara yang lain adalah mencari 2 pangkat berapa yang jika di mod 7 sama dengan 1, kita ketahui 2^3 % 7 = 1, jadi

(2 ^ 3) % 7 = 1

(2 ^ 2012) % 7 = (2 ^ (3*670+2)) %7
= ((2^3 % 7)^670 * (2^2 % 7)) % 7
= (1^670 * 4) % 7
= 4

Dan silahkan pakai cara apapun untuk mendapatkannya :D, semua cara benar, dan tergantung yang mana enaknya dipakai menurut anda.

Mungkin anda pernah mendengar hal seperti ini, 345^1234 berapakah dua angka paling kanan dari hasilnya? Harusnya anda bisa mengerjakan soal seperti ini, tinggal ubah menjadi (345^1234) % 100 = (45^1234) % 100, ya dan kerjakan seperti yang saya terangkan, sekarang jadi cukup mudahkan?

Dalam Competitive Programming

Biasanya digunakan jika jawabannya problem tersebut sangat besar sehingga tidak bisa ditampung dalam int64 (Pascal) atau long long (C++), sehingga perlu di mod, di soal biasanya ditulis harus di mod berapa, jadi jika anda menambahkan, atau mengalikan hasil jawaban sekarang, selalu ingat untuk memodulokan jawaban anda, kalau tidak, akan terjadi overflow.

Mungkin itu dulu yang saya tulis untuk post kali ini, ternyata cukup panjang juga, jika ada pertanyaan silahkan tulis di komentar, jika saya mampu bantu, saya akan bantu :D.