TLE-oj Cup Round 12 - Nghịch đảo modulo
Xem PDF
Nộp bài
Điểm:
1600 (thành phần)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
MODINV.inp
Output:
MODINV.out
Tác giả:
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, bf, C, C++, Haskell, Java, javascript, NASM, Pascal, Perl, scratch, text
Lưu ý: bài này không được dùng ngôn ngữ C++17 và C++20, cũng như Python.
Lưu ý 2: trong C++ có cấu trúc dữ liệu unsigned long long cho phép lưu số nguyên từ 0 đến 2^{64} - 1.
Cho ba số nguyên n, m, r (0 \le n, r < 2^m). Tìm một số nguyên x (0 \le x < 2^m) sao cho n \times x - r chia hết cho 2^m.
Input, Output và Subtasks
Input: (MODINV.inp)
- Dòng đầu tiên gồm số nguyên dương t \le 10^6 - số truy vấn.
- t dòng tiếp theo mỗi dòng gồm ba số nguyên n, m, r (1 \le m \le 64).
Output: (MODINV.out)
- Gồm t dòng, dòng thứ i là kết quả truy vấn thứ i. Nếu không tìm được số nguyên nào in ra -1, nếu có nhiều số in ra số nhỏ nhất.
Subtasks
- Subtask 1 (20\%): m \le 20, t = 1.
- Subtask 2 (20\%): m \le 32.
- Subtask 3 (10\%): m \le 60.
- Subtask 4 (20\%): m \le 63.
- Subtask 5 (30\%): Không có giới hạn gì thêm.
Sample
Input (MODINV.inp)
2
5 3 7
5 4 6
Output (MODINV.out)
3
14
Note
- 5 \times 3 - 7 = 8 chia hết cho 8.
- 5 \times 14 - 6 = 64 chia hết cho 16.
Bình luận