Đồng dư và nghịch đảo Mudule
Xác suất bốc thăm Hội xuân (ndmd)
Nộp bàiPoint: 1
Trong lễ hội xuân ở quảng trường Võ Nguyên Giáp, một thùng phiếu có A viên bi đỏ và B viên bi xanh. Nếu rút ngẫu nhiên 1 viên, xác suất rút được bi đỏ là phân số A / (A + B). Hãy in ra xác suất này dưới dạng một số nguyên modulo 998244353 (một mô đun thường dùng trong các bài toán xác suất lập trình thi đấu).
Dữ liệu vào: Hai số nguyên dương A và B.
Kết quả ra: Giá trị của A * nghịch đảo(A + B) modulo 998244353.
Ràng buộc: 1 <= A, B <= 10^6.
Ví dụ:
Input:
1 1
Output:
499122177
Sắp xếp các phân số nghịch đảo (ndmd)
Nộp bàiPoint: 1
Cho N phân số, mỗi phân số có dạng 1/X. Thay vì tính toán trực tiếp với số thập phân, em hãy chuyển đổi mỗi phân số 1/X thành giá trị nghịch đảo của X theo mô đun 10^9+7, sau đó tính tổng của N giá trị nghịch đảo đó và lại lấy dư cho 10^9+7 một lần nữa.
Dữ liệu vào: Dòng đầu là số N. Dòng thứ hai chứa N số nguyên dương X1, X2, ..., Xn.
Kết quả ra: Tổng các phân số nghịch đảo theo mô đun 10^9+7.
Ràng buộc: 1 <= N <= 10^5; 1 <= Xi <= 10^6.
Ví dụ:
Input:
2
2 3
Output:
833333340
Hành trình xe buýt Thái Nguyên (ndmd)
Nộp bàiPoint: 1
Một tuyến xe buýt chạy vòng tròn qua M bến (đánh số từ 0 đến M-1). Mỗi lần di chuyển, xe đi qua đúng K bến. Hiện tại xe đang ở bến 0, hỏi xe cần di chuyển ít nhất bao nhiêu lần để đến được bến số 1? Trạm 1 có thể đạt được nếu tồn tại số lần đi X sao cho K * X đồng dư 1 (mod M). Đây chính là định nghĩa của nghịch đảo mô đun.
Dữ liệu vào: Hai số nguyên dương K và M.
Kết quả ra: Số lần di chuyển X ít nhất. Nếu không bao giờ tới được bến 1 (do K và M không nguyên tố cùng nhau), in ra -1.
Ràng buộc: 1 <= K < M <= 10^9.
Ví dụ:
Input:
3 8
Output:
3