Đề bài

Robot thám hiểm

Một con robot thám hiểm sao Hỏa tên là “Mars Rover” của cơ quan vũ trụ Nga đã không hoạt động. Để khôi phục nó, cần phải tăng thêm công suất cho pin. Pin của Rover là một số nguyên dương.

• Công suất hiện tại của pin là \(a\)
• Để khôi phục hoạt động của nó, cần phải tăng công suất lên giá trị \(b\)
• Từ Trái Đất có thể gửi đến Rover hai loại tín hiệu đặc biệt:
• Tín hiệu X: tăng công suất lên 1
• Tín hiệu Y: tăng công suất lên 2

Tuy nhiên, nếu công suất của pin là bội số của một số nguyên \(c\), thì Rover sẽ bị lỗi và ngừng hoạt động.

Yêu cầu: Cho \(a, b, c\) — xác định số lượng tín hiệu ít nhất cần truyền tới Rover để khôi phục hoạt động mà không gây lỗi.

Dữ liệu vào

Một dòng gồm ba số nguyên \(a, b, c\) (\(1 \leq a < b \leq 10^9\), \(2 \leq c \leq 10^9\)), đảm bảo \(a\) và \(b\) không phải là bội của \(c\).

Dữ liệu ra

Một số nguyên duy nhất là số tín hiệu ít nhất cần truyền tới Rover.

Giới hạn

• 25% số điểm: \(1 \leq a < b \leq 15\), \(2 \leq c \leq 15\)
• 25% số điểm: \(1 \leq a < b \leq 10^5\), \(2 \leq c \leq 10^5\)
• 25% số điểm: \(1 \leq a < b \leq 10^9\), \(c = 2\)
• 25% số điểm: \(1 \leq a < b \leq 10^9\), \(2 \leq c \leq 10^9\)

Sample Input 1

2 7 3

Sample Output 1

3

Sample Input 2

4 10 3

Sample Output 2

4

Giải thích

• Với input 2 7 3: Các bước truyền tín hiệu sẽ như sau: \(2 \to 4 \to 5 \to 7\)
• Với input 4 10 3: Các bước truyền tín hiệu: \(4 \to 5 \to 7 \to 8 \to 10\) (bỏ qua 6 và 9 vì chia hết cho 3)