Mini-project Part 4: Number Theory Calculator

This project combines all of Part 4 into one program that answers many questions at once — a problem shape that often appears in OSN under the name "queries".

The problem

Pak Dengklek's calculator. Pak Dengklek wants one program that can answer q questions about numbers. Each question starts with one type number:

Type Extra input What is printed
1 a b GCD(a, b)
2 a b LCM(a, b)
3 a b m aᵇ mod m
4 n PRIMA or BUKAN ("prime" / "not prime")
5 p q the fraction p/q in simplest form, format p/q
6 x y p (x / y) mod p, with p prime

Constraints. q ≤ 100,000. For types 1, 2, 3, and 5, the values go up to 10¹⁸ (the LCM is guaranteed to fit in long long). For type 4, n ≤ 10¹² and the number of type 4 questions is at most 1,000. For type 6, p is prime and y is not divisible by p.

Time limit 2 seconds.

Sample input:

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

Sample output:

6
36
24
PRIMA
8/3
333333339

What to build

One file containing small functions, each of which you have already written in Chapters 14 and 15:

  • fpb(a, b) (GCD) — the Euclidean algorithm.
  • kpk(a, b) (LCM) — using fpb, with an order of operations that is safe from overflow.
  • pangkat_mod(a, b, m) ("modular power") — fast modular exponentiation.
  • prima(n) ("prime") — square-root test, with i * i <= n.
  • invers(y, p) ("inverse") — using pangkat_mod(y, p - 2, p).

Then main reads q, reads the type of each question, and calls the matching function.

Counting the time

Before writing, check whether the plan fits:

Type Cost of one question Maximum count Total
1, 2, 5 O(log 10¹⁸) ≈ 90 100,000 9 million steps
3, 6 O(log 10¹⁸) ≈ 60 100,000 6 million steps
4 O(√n) = 10⁶ 1,000 10⁹ steps

The last row is the trap. The first five types are cheap because all of them have logarithmic cost; the prime-test type alone already eats up the whole time limit.

Two levels of solution:

  • Enough for partial points. The square-root test as-is: for (long long i = 2; i * i <= n; i++). About 10⁹ steps in the worst case — right at the edge of the time limit, and over it if the data is slightly heavier.
  • Full solution. Prepare a sieve of Eratosthenes (Chapter 07) up to 10⁶ once at the start, then for type 4 it is enough to try dividing n by the prime numbers produced by the sieve. There are only 78,498 prime numbers below 10⁶, so the cost of one question drops by about 12 times — to about 8 × 10⁷ steps for 1,000 questions, safe.

Do the first version first, measure its time with 1,000 type 4 questions with the value 999999000001 (a prime number, the worst case), and only then do the second version.

For a much larger number q of type 4 questions, both methods above still lose, and what is needed is a probabilistic primality test such as Miller-Rabin — outside the scope of this book. The problem's constraints are deliberately chosen so that a solution with the sieve is enough.

Hints

  • Every type is long long. A single leftover int will break the answer for large input.
  • Use "\n", not endl. For 100,000 lines of output, the difference is noticeable.
  • Add ios::sync_with_stdio(false); cin.tie(nullptr); as the first two lines in main. Together they speed up cin/cout several times on large input — a standard habit in contests.
  • Test each function on its own before combining them. That is the point of splitting into functions.

Files

Compile and run:

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

Done?

If all six question types are correct, and you can explain why the prime test needs special treatment while the other five types do not — this project is finished.

Continue to Chapter 16 — The sum and product rules, the last part of this book.