Cho số nguyên dương A và một số nguyên tố M. Hãy tìm nghịch đảo mô đun của A theo mô đun M. Biết rằng nghịch đảo mô đun của A modulo M là một số nguyên dương X (0 < X < M) thỏa mãn (A * X) chia M dư 1. Nếu không tồn tại, in ra -1.

Dữ liệu vào: Một dòng chứa hai số nguyên A và M cách nhau một khoảng trắng.

Kết quả ra: Số nguyên X cần tìm.

Ràng buộc: 1 <= A < M <= 10^9; M là số nguyên tố.

Ví dụ:

Input:

3 11

Output:

4

Trong một trò chơi mật mã của câu lạc bộ lập trình, các bạn học sinh cần giải phương trình đồng dư: A * X đồng dư với B (modulo M). Hãy giúp các bạn tìm ra số X nhỏ nhất không âm thỏa mãn yêu cầu này. Đảm bảo A và M nguyên tố cùng nhau.

Dữ liệu vào: Ba số nguyên A, B, M cách nhau khoảng trắng.

Kết quả ra: Số nguyên X thỏa mãn (0 <= X < M).

Ràng buộc: 1 <= A, B < M <= 10^9; UCLN(A, M) = 1.

Ví dụ:

Input:

4 2 7

Output:

4

Khi làm việc với các số rất lớn, ta thường phải tính toán theo một mô đun M. Cho ba số nguyên A, B và M. Đề bài yêu cầu tính giá trị của phân thức (A / B) theo mô đun M. Phép tính này được định nghĩa là (A * (nghịch đảo của B theo mô đun M)) mod M.

Dữ liệu vào: Ba số nguyên A, B, M.

Kết quả ra: Kết quả của phép chia theo mô đun M. Nếu không thể thực hiện do B và M không nguyên tố cùng nhau, in ra -1.

Ràng buộc: 1 <= A, B < M <= 10^9; M là số nguyên tố lớn hơn 2.

Ví dụ:

Input:

8 3 13

Output:

7

Cho ba số nguyên dương N, K và P. Hãy tính số lượng tổ hợp chập K của N (số cách chọn K phần tử từ N phần tử) theo mô đun P. Vì kết quả rất lớn, em cần tính giai thừa của tử số và dùng nghịch đảo mô đun để xử lý phần giai thừa dưới mẫu số. Đảm bảo P là số nguyên tố.

Dữ liệu vào: Ba số nguyên N, K, P.

Kết quả ra: Phần dư của phép tính tổ hợp khi chia cho P.

Ràng buộc: 1 <= K <= N <= 10^5; P = 10^9+7.

Ví dụ:

Input:

5 2 1000000007

Output:

10

Cho hai phân số a/b và c/d. Hãy tính tổng của hai phân số này, sau đó in ra kết quả dưới dạng một số nguyên P thỏa mãn công thức của nghịch đảo mô đun: P = (Tử số * nghịch đảo của Mẫu số) mod 1000000007.

Dữ liệu vào: Bốn số nguyên dương a, b, c, d.

Kết quả ra: Kết quả tổng hai phân số theo mô đun 10^9+7.

Ràng buộc: 1 <= a, b, c, d <= 10^6.

Ví dụ:

Input:

1 2 1 3

Output:

833333340

Cho một cấp số nhân có số hạng đầu là 1, công bội là Q. Hãy tính tổng N số hạng đầu tiên của dãy theo mô đun 10^9+7. Công thức tổng là (Q^N - 1) / (Q - 1). Em cần dùng lũy thừa nhị phân kết hợp nghịch đảo mô đun để thực hiện phép chia này.

Dữ liệu vào: Hai số nguyên dương Q và N.

Kết quả ra: Tổng của cấp số nhân modulo 10^9+7.

Ràng buộc: 2 <= Q <= 10^6; 1 <= N <= 10^12.

Ví dụ:

Input:

2 3

Output:

7

Tính a mũ b chia dư cho c với a, b, c là các số nguyên dương

Ràng buộc: ~1 \leq a, c \leq 10^4~; ~1 \leq b \leq 10^6~

Input 01:

2 1000000 10

Nhập như trên tức là 2 mũ 1000000 chia dư cho 10

Output 01:

6

Giải thích: 2 mũ 1000000 chia dư cho 10 kết quả sẽ bằng 6

Input 02:

5 999999 10

Output 02:

5

Cho N số nguyên, bạn hãy tính tích các số này và chia dư cho 1086600067

Ràng buộc:

~1 \leq N \leq 10^5~

Các số là nguyên dương không quá ~10^6~

Input:

5
153 747 236 481 789

Output:

600664944

Sunny đang học môn toán và hôm nay nhận được bài tập về cách tính tổng các ước số của một số nguyên dương. Nhiệm vụ là tìm tổng các số bé hơn hoặc bằng N và không phải là ước số của N.

Dữ liệu đầu vào: Dòng đầu tiên chứa một số nguyên dương N (1 ≤ N ≤ 10^14).

Dữ liệu đầu ra: In ra một số duy nhất, là kết quả của bài toán được chia lấy dư cho 10^9 + 7.

Input 01:

7

Output 01:

20

Giải thích: N=7: Các ước số của 7 là 1 và 7. Tổng các số từ 1 đến 7 là 1+2+3+4+5+6+7=28. Tổng các ước là 1+7=8. Kết quả là 28-8=20.

Input 01:

12

Output 02:

50

Giải thích: Với N=12: Các ước số của 12 là 1, 2, 3, 4, 6, 12. Tổng các số từ 1 đến 12 là 1+2+..+ 12=78. Tổng các ước là 1+2+3+4+6+12=28. Kết quả là 78-28=50.

Cho a, b, c là các số nguyên dương, hãy tính a lũy thừa b chia dư cho c

Ràng buộc: ~1 \leq a, b, c \leq 10^6~

Input:

2 1000000 10

Tính 2 mũ 1000000 chia dư cho 10

Output:

6

Bạn hãy tính N giai thừa và chia dư cho 10^9 + 7

Ràng buộc: ~1 \leq N \leq 10^6~

Input 01:

5

Output 01:

120

Input 02:

100

Output 02:

437918130

Thuật toán Euclid mở rộng không chỉ tìm UCLN mà còn giúp tìm nghịch đảo mô đun với bất kỳ số M nào (không nhất thiết là số nguyên tố). Cho hai số nguyên dương A và M. Hãy áp dụng thuật toán Euclid mở rộng để tìm nghịch đảo của A theo mô đun M.

Dữ liệu vào: Hai số nguyên A và M.

Kết quả ra: Nghịch đảo của A modulo M. Nếu UCLN(A, M) khác 1, in ra -1.

Ràng buộc: 1 <= A < M <= 10^9. (M có thể là hợp số).

Ví dụ:

Input:

3 10

Output:

7