Dan kita akan membahas tentang math lagi. Jangan serem dulu liat namanya "Linear Diophantine", sebenarnya itu namanya doang yang keren, tapi sebenarnya tidak terlalu susah teorinya. Sederhananya yang ingin kita solve adalah soal seperti ini :

ax + by = c

Dimana a, x, b, y, dan c adalah bilangan bulat (integer), dan kita telah mengetahui nilai dari a, b, dan c. Kita diminta mencari semua pasangan x dan y yang memenuhi persamaan diatas.

Level	Basic
Type	Math
Requirement	Algebra
Similar	GCD and LCM Extended Euclid

Diophantine Equation

Perlu diketahui linear diophantine adalah salah satu dari diophantine equation.
Apakah diophantine equation?
Itu adalah persamaan yang melibatkan semua variable itu merupakan bilangan bulat (integer), tidak boleh bilangan real (float).
Terus menurut Wikipedia, kalau aku tidak salah terjemahin, dia memiliki persamaan yang lebih sedikit dari unknown variable (variable yang musti dicari), jadi dengan persamaan yang ada, kita tidak bisa mendapatkan variable yang belum diketahui itu dengan pasti berapa angkanya (lebih dari satu kemungkinan).

Kalau kurang jelas, jadi langsung saja ke contohnya.
Misalkan kita memiliki persamaan berikut

2x + 3y = 99
x + y = 43

Soal ini bisa kita selesaikan dengan mudah, dan mendapatkan hasil x = 30 dan y = 13 kan?

Nah misalkan kita hanya memiliki persamaan berikut.

2x + 3y = 99

Kita disuruh mencari x dan y.
Disini kita tidak dapat mencari dengan pasti apa x dan y tersebut, karena bisa lebih dari satu jawaban.
Misalkan x = 0, maka y = 33
Misalkan x = 1, maka y = 32,33
Misalkan x = 2, maka y = 31,66
dst...

Jadi bisa banyak banget penyelesaiannya...
Nah jika kita menambah constraint jika x dan y nya hanya bisa integer, hal itu menjadi lumayan ribet, karena kita tidak boleh lagi memilih sembarang x untuk mendapatkan y.
Hanya x tertentu saja yang dapat membuat y menjadi bilangan integer.
Seperti x = 0, maka y = 33
Atau x = 3, maka y = 31
Atau x = 6, maka y = 29
dst...

Nah itulah yang akan kita bahas nanti, persamaan diatas disebut Linear Diophantine.

Linear Diophantine

Problem linear diophantine, generalnya bisa dibilang seperti ini,

ax + by = c

Tetapi sebenarnya yang linear diophantine itu menyelesaikan problem seperti ini

ax + by = gcd(a, b)

Dimana semua variable integer, dan kita hanya mengetahui a dan b, kita disuruh mencari x dan y yang memungkinkan.

Sebenarnya lumayan mudah menyelesaikannya, langsung saja ke contoh, yang ingin kita selesaikan adalah ini

18x + 13y = gcd(18, 13)
atau
18x + 13y = 1

Dan beginilah penyelesaiannya :

18 - 13*1 = 5 ...(1)
13 -  5*2 = 3 ...(2)
 5 -  3*1 = 2 ...(3) 
 3 -  2*1 = 1 ...(4)

Pertama kita perlu membuat persamaan - persamaan diatas, caranya adalah, pertama - tama kita mengambil 18 dan 13, terus yang besar yaitu 18, dikurang dengan kelipatan angka yang lebih kecil, yaitu 13. Kelipatan 13 tersebut yang kita pilih adalah kelipatan terbesar yang masih lebih kecil dari 18.
Sesudah itu kita ambil angka yang kecil tersebut dengan angka hasilnya, dan kita lakukan hal yang serupa. Lakukan begitu terus, sampai hasilnya itu merupakan gcd(18, 13) yaitu 1.

Setelah selesai, kita akan mengubahnya seperti ini

Kita masukan persamaan (3) ke dalam persamaan (4)
3   -         2*1 = 1
3*1 - (5 - 3*1)*1 = 1
3*1 - 5*1 + 3*1   = 1
3*2 - 5*1         = 1 ...(5)

Masukan persamaan (2) ke persamaan (5)
         3*2 - 5*1 = 1
(13 - 5*2)*2 - 5*1 = 1
  13*2 - 5*4 - 5*1 = 1
        13*2 - 5*5 = 1 ...(6)

Masukan persamaan (1) ke persamaan (6)
          13*2 - 5*5 = 1
13*2 - (18 - 13*1)*5 = 1
13*2 - 18*5 + 13*5   = 1
13*7 - 18*5          = 1 ...(7)

Lihat persamaan (70, kita mendapatkan 13*7 - 18*5 = 1, dan yang kita cari adalah 18x + 13y = 1, jadi bisa kita simpulkan kalau x = -5, dan y = 7 kan?
Problem solved :D...
Tapi seperti yang aku notice sebelumnya, linear diophantine memiliki lebih dari satu solusi, dan bagaimana mendapatkan solusi yang lain?

Itu bisa didapat dengan menggunakan lcm dari 18 dan 13, lcm(18,13) = 234 = 18*13, jadi dari persamaan (7) kita lakukan hal berikut

13*7 - 18*5                   = 1
13*7 - 18*5 + (18*13 - 18*13) = 1
13*7 + 13*18 - 18*5 - 18*13   = 1
13*25 - 18*18                 = 1 ...(8)

Jadi kita mendapatkan solusi yang lain, yaitu 13*25 - 18*18 = 1, jadi x = -18, dan y = 25.
Dan kita bisa mendapatkan yang lainnya dengan melakukan hal yang sama berulang - ulang.

Untuk generalnya, bisa dijadikan begini

x = -5 + n*(lcm(18, 13)/18)
y =  7 - n*(lcm(18, 13)/13)

Untuk n bisa bilangan bulat apa saja, bisa negatif, 0, atau positif.

Untuk lebih general, untuk persamaan ax + by = gcd(a,b), maka

x = x0 + n*(lcm(a, b)/a)
y = y0 - n*(lcm(a, b)/b)

atau

x = x0 + n*(b/gcd(a, b))
y = y0 - n*(a/gcd(a, b))

Dengan x0 dan y0 dicari dari cara sebelumnya.

General Problem Linear Diophantine

Misalkan kita ingin mencari solusi dari persamaan seperti ini

ax + by = c

Dengan a, b, c diketahui, dan semua variable adalah integer.

Caranya hampir sama seperti cara sebelumnya, misalkan kita diberi persamaan seperti ini

18x + 13y = 150

Jika diberi seperti ini, kita harus mencari x0 dan y0 untuk persamaan berikut terlebih dahulu

18x + 13y = gcd(18,13)
18x + 13y = 1

Dan persamaan diatas adalah persamaan yang kita bahas sebelum topic ini.
Dan kita sudah mendapatkan x0 = -5 dan y0 = 7 dari persamaan (7) sebelumnya.

Dari persamaan (7) kita bisa utak - atik lagi

13*7 - 18*5       = 1
(13*7 - 18*5)*150 = 1*150
13*1050 - 18*750  = 150

Dan kita menemukan x0 dan y0 yang baru, yaitu x0 = -750, dan y0 = 1050, untuk mencari kemungkinan solusi lain, silahkan menggunakan cara sebelumnya yang menggunakan lcm.

Seandainya, gcd(a,b) bukan 1, misalnya gcd(a,b) = 2, maka jika dalam ax + by = 99, maka hal tersebut tidak memiliki penyelesaian, karena tidak ada bilangan bulat yang dikali dengan 2 menghasilkan angka 99.

Jadi tidak semuanya yang memiliki persamaan ax + by = c itu mempunyai solusi, jika c tidak habis dibagi dengan gcd(a,b) maka persamaan tersebut tidak memiliki solusi.

Contoh Problem

Soal Packing

Banyak problem yang menggunakan linear diophantine, contoh sederhananya adalah, kita memiliki 2 box, masing - masing box bisa menampung sebanyak a dan b barang. Suatu box harus diisi full, tidak boleh setengah - setengah. Diberikan sejumlah c barang, tentukan apakah semua barang itu bisa di pack dengan sempurna (tidak ada yang tersisa di luar box, dan dalam suatu box isinya full). Kalau bisa, berapa banyak masing - masing dari tipe box yang dibutuhkan?

Ini obvious linear diophantine dengan persamaan ax + by = c. Bedanya adalah, x dan y tidak boleh negatif. Jadi kita menambahkan constraint dari solusi akhir, dan tidak jarang ini hanya bisa menghasilkan satu solusi.

Misalkan diberikan a = 18 dan b = 13 (sama seperti sebelumnya), dan c = 30.
Maka kita nanti akan mendapatkan ini

13*7 - 18*5      = 1
(13*7 - 18*5)*30 = 1*30
13*210 - 18*150  = 30

Dengan x = -150, dan y = 210, ini tidak memenuhi karena x < 0. Jadi kita mencari solusi lain, dengan cara sebelumnya...

x =   x0 + n*(lcm(a, b)/a)

x = -150 + n*(lcm(18,13)/18)

x = -150 + 13n



y =  y0 - n*(lcm(a, b)/a)

y = 210 - n*(lcm(18,13)/13)

y = 210 - 18n

Untuk membuat x tidak menjadi negatif, maka kita harus mengambil n paling kecil yang membuat x menjadi positif. Mengambil yang minimal agar y tidak menjadi negatif, karena semakin besar n semakin kecil y.
Dan kita akan mendapatkan n = 12, agar x menjadi positif, maka x menjadi 6 dan y menjadi -6. Karena sudah dipilih n terkecil untuk menjadikan x positif, n yang kurang dari 12 sudah pasti tidak mungkin, karena x akan menjadi negatif, n yang lebih besar dari 12 juga tidak mungkin karena nilai y akan semakin negatif. Jadi tidak ada solusi untuk c = 30

Kita coba untuk c = 75.

13*7 - 18*5      = 1
(13*7 - 18*5)*75 = 1*75
13*525 - 18*375  = 75

x =   x0 + n*(lcm(a, b)/a)
x = -375 + n*(lcm(18,13)/18)
x = -375 + 13n

y =  y0 - n*(lcm(a, b)/a)
y = 525 - n*(lcm(18,13)/13)
y = 525 - 18n

Sama seperti sebelumnya, kita mencari n minimum yang membuat x positif. Yaitu n = 29, dan x menjadi 2, dan y menjadi 3, dan ini merupakan jawaban yang valid. Kemudian jika kita naikan n = 30, maka x = 15, tetapi y = -15, dan bukan merupakan jawaban yang valid lagi.
Sehingga solusi untuk c = 75 hanya ada satu yaitu x = 2, dan y = 3.

Soal Ketemuan

Pasti anda pernah ketemu soal seperti ini, si A mulai pergi ke suatu tempat pada hari ke 'amulai', dan akan ke tempat itu setiap selang 'aselang' hari. Sedangkan si B mulai pergi dari hari ke 'bmulai' dan akan pergi setiap 'bselang' hari. Pada hari keberapa mereka akan pergi bersama - sama?

Biasanya kita menggunakan cara kuli untuk menghitung soal seperti diatas ._.
Misalkan contohnya

amulai = 3
aselang = 5
bmulai = 4
bselang = 7

Kita akan menghitung seperti ini, yaitu didata kapan setiap orang pergi

A =  3  8 13 18 23
B =  4 11 18 25 32

Oh ternyata hari ke 18 mereka bakal pergi bersama - sama.

Dan adakah solusi matematikanya? Jawabannya ada :D...

Kita definisikan hari A pergi sebagai 'a', dan hari B pergi sebagai 'b', sehingga kita memperoleh

a = amulai + x*aselang
b = bmulai + y*bselang

Dan yang kita mau adalah hari A pergi sama dengan hari B pergi yaitu a = b, jadi

amulai + x*aselang = bmulai + y*bselang
x*aselang - y*bselang = bmulai - amulai

x*5 - y*7 = 4 - 3
5x + (-7)y = 1

Dan itu adalah linear diophantine, kita ingin mencari x dan y nya kan, dan yang pasti x dan y bukan bilangan negatif. Jika sudah menemukannya tinggal memasukkannya ke dalam persamaan untuk mendapatkan nilai a atau b.
Ini bisa di extend menjadi lebih dari satu orang, tetapi harusnya bisa anda pikirkan caranya sendiri.

Untuk Inverse Modulo

Hal ini bisa digunakan untuk inverse modulo.
Apakah inverse modulo? Yaitu modulo yang bekerja pada pembagian.

Diketahui modulo tidak bekerja dalam pembagian, maksudnya

(a / b) % md != ((a % md) / (b % md)) % md

Nah, jika a habis dibagi b, hal itu bisa diakali, sehingga

(a / b) % md = (a * c) % md = ((a % md) * (c % md)) % md

Nah dalam mencari variable c yang pas, salah satu caranya perlu menggunakan linear diophantine.
Hal ini akan dibahas di post yang lainnya.

Extended Euclid

Extended Euclid adalah algoritma yang digunakan dalam pemprograman untuk menyelesaikan linear diophantine. Caranya mirip - mirip dengan yang saya jelaskan, tetapi kodenya jauh berbeda, ini akan dibahas di post yang lainnya.

Dan ternyata lumayan pegel menulis artikel berikut, semoga bermanfaat :D.

P.S : jika ada yang salah, baik teori, nulis atau apalah, tolong diberitahu, karena aku juga tidak expert - expert amat dalam hal ini...

P.P.S : harusnya ini tidak terlalu penting dalam OSN, tetapi good to know, jadi pas Pelatnas 1 jika diajari Extended Euclid, sudah memiliki dasar, bandingkan dengan saya yang pas Pelatnas 1 masih ngeblank ini code Extended Euclid gimana cara kerjanya (karena saya cuman copas dari buku pegangan LOL)

P.P.P.S : harusnya untuk angka yang kecil, dikuli lebih cepat dibandingkan pakai ginian ._.