Troll Việt Nam
Minh rất thích lập trình, hôm nay anh ấy gặp một bài toán có độ khó 3501 codeforces như sau:
Cho ba số nguyên dương n,l,r. Nhiệm vụ của bạn là đếm số cặp dãy số a và b độ dài n sao cho thỏa mãn hai điều kiện sau:
- l\le a_i\le r,l\le b_i\le r với mọi i từ 1 đến n.
- a_1\times a_2...\times a_n=b_1\times b_2...\times b_n.
Input, Output và Subtasks
Input
- Dòng đầu tiên gồm duy nhất một số nguyên dương t là số testcase (1\le t\le 5).
- t dòng tiếp theo, mỗi dòng gồm ba số nguyên dương n,l,r\ (1\le n,l,r\le 10^6).
Output
- Với mỗi testcase, in ra kết quả trên một dòng:
- Gọi ans là số cặp dãy số thỏa mãn.
- Nếu ans<998244353 thì in ra ans\ mod\ 998244353 (với mod là phép chia lấy dư).
- Ngược lại thì in ra
-1.
Subtasks
- Subtask 1 (10\%): n=1.
- Subtask 2 (10\%): n\le 10,r-l\le 6.
- Subtask 3 (20\%): n,l,r\le 100.
- Subtask 4 (30\%): n,l,r\le 1000.
- Subtask 5 (30\%): Không có ràng buộc gì thêm.
Sample
Input
2
1 1 1
123456 1 69420
Output
1
-1
Cặp điểm tình bạn
Có 2\times n + 1 điểm trên mặt phẳng tọa độ, hai điểm phân biệt (x,y) và (a,b) được gọi là tình bạn khi và chỉ khi:
- a = x hoặc b = y.
Ngoài ra tình bạn luôn chung thủy nên mỗi điểm chỉ có tối đa một tình bạn.
Yêu cầu: cho 2\times n + 1 điểm phân biệt, nếu ta loại bỏ một điểm bất kì thì có thể tạo ra n cặp điểm tình bạn không.
Input, Output and Subtask
Input (FRIEND.inp)
- Dòng đầu tiên chứa một số nguyên dương n (1≤n≤10^5)
- 2\times n + 1 dòng tiếp theo, mỗi dòng có hai số nguyên dương x_i và y_i (1\le x_i, y_i \le 2\times n + 1).
Output (FRIEND.out)
- In ra 2\times n + 1 dòng. Tại dòng thứ i, nếu loại bỏ điểm i thì tạo được n cặp điểm tình bạn thì in
YEShoặcNOvới trường hợp còn lại.
Subtask
- Subtask 1 :(20\%) n\le 100.
- Subtask 2 :(80\%) không có giới hạn gì thêm.
Sample
FRIEND.inp
2
1 2
3 2
4 5
3 1
1 5
FRIEND.out
YES
NO
YES
YES
NO
Truy lùng vị trí
Cabral đang truy lùng ataide trên mặt phẳng hệ tọa độ Descartes, biết ataide ban đầu ở vị trí (0;0).
Tại mỗi bước ataide sẽ chọn một hướng đi lên trên, xuống dưới, trái hoặc phải. Anh ấy sẽ tiếp tục đi thẳng đến khi nào gặp điểm mà anh ấy chưa từng đi qua, thì anh sẽ dừng lại và đi theo hướng tiếp theo. Tổng cộng anh ấy đã chọn chính xác n hướng.
Yêu cầu: biết các hướng đi của ataide hãy tìm điểm mà ataide ở đó sau n hướng đi.
Input, Output and Subtask
Input (TRUYLUNG.inp)
- Dòng đầu tiên chứa một số nguyên dương n và m (1≤n≤10^5)
- Dòng tiếp theo chứa xâu s có n kí tự
L,R,U,Dtương ứng với:
Lđi sang trái.
Rđi sang phải.
Uđi lên trên.
Dđi xuống dưới.
Output (TRUYLUNG.out)
- Dòng đầu tiên gồm hai số nguyên x và y tương ứng với vị trí (x,y) của ataide sau n hướng đi.
Subtask
- Subtask 1: (20\%) s_i=s_{i+1} với i\le n-1.
- Subtask 2: (30\%) n\le 1000.
- Subtask 3: (50\%) không có giới hạn gì thêm.
Sample
TRUYLUNG.inp
4
LRLR
TRUYLUNG.out
2 0
Note
Các vị trí mà ataide đã đi qua là (0;0)\rightarrow(-1;0)\rightarrow(1;0)\rightarrow(-2;0)\rightarrow(2;0).
Số nguyên tố
I love Quỳnh Anh - mondellbit009
Quỳnh Anh mới học về số nguyên tố. Bây giờ, cậu đang có 2 số nguyên dương l, r và cậu muốn biết số lượng số nguyên tố trong đoạn [l, r] là bao nhiêu. Bạn hãy đếm giúp Quỳnh Anh nhé.
Input, Output and Scoring
Input
- 2 số nguyên dương l, r (1 \le l \le r \le 10^9).
Output
- In ra kết quả thỏa mãn.
Scoring
- Subtask 1 (20\%): 1 \le l \le r \le 10^3.
- Subtask 2 (30\%): 1 \le l \le r \le 10^6.
- Subtask 3 (50\%): Không giới hạn gì thêm.
Test
Input
69 420
Output
64