Mini-proyek Bagian 4: Kalkulator Teori Bilangan

Proyek ini menggabungkan seluruh Bagian 4 menjadi satu program yang menjawab banyak pertanyaan sekaligus — bentuk soal yang sering muncul di OSN dengan nama "kueri".

Soalnya

Kalkulator Pak Dengklek. Pak Dengklek ingin satu program yang bisa menjawab q pertanyaan tentang bilangan. Setiap pertanyaan diawali satu angka jenis:

Jenis Masukan tambahan Yang dicetak
1 a b FPB(a, b)
2 a b KPK(a, b)
3 a b m aᵇ mod m
4 n PRIMA atau BUKAN
5 p q pecahan p/q paling sederhana, format p/q
6 x y p (x / y) mod p, dengan p prima

Batasan. q ≤ 100.000. Untuk jenis 1, 2, 3, dan 5, nilainya sampai 10¹⁸ (KPK dijamin muat di long long). Untuk jenis 4, n ≤ 10¹² dan banyaknya pertanyaan jenis 4 tidak lebih dari 1.000. Untuk jenis 6, p prima dan y tidak habis dibagi p.

Batas waktu 2 detik.

Contoh masukan:

6
1 48 18
2 12 18
3 2 10 1000
4 999999000001
5 48 18
6 10 3 1000000007

Contoh keluaran:

6
36
24
PRIMA
8/3
333333339

Yang harus dibuat

Satu berkas berisi fungsi-fungsi kecil, masing-masing sudah kamu tulis di Bab 14 dan 15:

  • fpb(a, b) — algoritma Euclid.
  • kpk(a, b) — memakai fpb, dengan urutan operasi yang aman dari luapan.
  • pangkat_mod(a, b, m) — pangkat modulo cepat.
  • prima(n) — uji akar, dengan i * i <= n.
  • invers(y, p) — memakai pangkat_mod(y, p - 2, p).

Lalu main membaca q, membaca jenis setiap pertanyaan, dan memanggil fungsi yang sesuai.

Perhitungan waktu

Sebelum menulis, periksa apakah rencananya masuk:

Jenis Biaya satu pertanyaan Jumlah maksimal Total
1, 2, 5 O(log 10¹⁸) ≈ 90 100.000 9 juta langkah
3, 6 O(log 10¹⁸) ≈ 60 100.000 6 juta langkah
4 O(√n) = 10⁶ 1.000 10⁹ langkah

Baris terakhir adalah jebakannya. Lima jenis pertama murah karena semuanya berbiaya logaritmik; satu jenis uji prima saja sudah menelan seluruh batas waktu.

Dua tingkat penyelesaian:

  • Cukup untuk sebagian nilai. Uji akar apa adanya: for (long long i = 2; i * i <= n; i++). Sekitar 10⁹ langkah pada kasus terburuk — di ambang batas waktu, dan lewat kalau datanya sedikit lebih berat.
  • Penyelesaian penuh. Siapkan saringan Eratosthenes (Bab 07) sampai 10⁶ satu kali di awal, lalu untuk jenis 4 cukup coba bagi n dengan bilangan-bilangan prima hasil saringan. Bilangan prima di bawah 10⁶ hanya ada 78.498, jadi biaya satu pertanyaan turun sekitar 12 kali lipat — menjadi sekitar 8 × 10⁷ langkah untuk 1.000 pertanyaan, aman.

Kerjakan versi pertama dulu, ukur waktunya dengan 1.000 pertanyaan jenis 4 bernilai 999999000001 (bilangan prima, kasus terburuk), baru kerjakan versi kedua.

Untuk q jenis 4 yang jauh lebih banyak, kedua cara di atas tetap kalah, dan yang dibutuhkan adalah uji prima probabilistik seperti Miller-Rabin — di luar cakupan buku ini. Batasan soal sengaja dipilih agar penyelesaian dengan saringan sudah cukup.

Petunjuk

  • Semua tipe long long. Satu saja int yang tersisa akan merusak jawaban untuk masukan besar.
  • Pakai "\n", bukan endl. Untuk 100.000 baris keluaran, bedanya terasa.
  • Tambahkan ios::sync_with_stdio(false); cin.tie(nullptr); sebagai dua baris pertama di main. Keduanya mempercepat cin/cout beberapa kali lipat pada masukan besar — kebiasaan baku di lomba.
  • Uji setiap fungsi sendiri-sendiri sebelum menggabungkannya. Itulah gunanya memecah menjadi fungsi.

File

Compile dan jalankan:

g++ -std=c++17 -O2 -o kalkulator projects/04-kalkulator-bilangan/starter.cpp
./kalkulator < projects/04-kalkulator-bilangan/contoh-masukan.txt

Sudah selesai?

Kalau keenam jenis pertanyaan benar, dan kamu bisa menjelaskan mengapa uji prima memerlukan perlakuan khusus sementara lima jenis lainnya tidak — proyek ini selesai.

Lanjut ke Bab 16 — Aturan penjumlahan dan perkalian, bagian terakhir buku ini.