LQDOJ Contest #5

Cho một hình vuông có \(15 \times 15\) ô vuông có màu đen hoặc trắng như sau:

Yêu cầu: Bạn hãy in ra màu của ô vuông nằm ở hàng thứ \(A\) (đếm từ trên xuống) và cột thứ \(B\) (đếm từ trái qua phải).

Input

• Chứa hai số nguyên dương lần lượt là \(A\) và \(B\) \((1 \le A,B \le 15)\).

Output

• In ra trang nếu ô vuông đó là màu trắng, in ra den nếu ô vuông đó màu đen.

Example

3 5

den

4 5

trang

Ngày xửa ngày xưa, ở vùng đất rộng lớn và huyền bí, có một ngôi làng có tên là làng LQDOJ nằm bên dòng sông êm đềm. Truyền thuyết kể rằng, ngôi làng này là nơi cư trú của ba phù thủy mạnh mẽ Small, cuom1999 và Flower_On_Stone. Ba phù thủy ấy không chỉ nổi tiếng với phép thuật mà còn với sự khéo léo trong việc sắp xếp, kết hợp các yếu tố tự nhiên để tạo ra những điều kỳ diệu.

Một ngày, ba phù thủy quyết định sử dụng sức mạnh của họ để tạo ra một loại phép thuật mới. Họ muốn tìm ra tất cả các bộ ba số nguyên dương sao cho tích của ba số đó không vượt quá một giá trị cho trước. Điều này sẽ giúp làng có thể sử dụng phép thuật này để tạo ra sức mạnh, hạnh phúc và thịnh vượng cho mọi người.

Tuy nhiên, để thực hiện phép thuật này, ba phù thủy cần lựa chọn các bộ ba số nguyên dương một cách chính xác và theo thứ tự tăng dần. Họ muốn đảm bảo rằng mọi kết quả đều được sắp xếp theo thứ tự, để từ đó có thể áp dụng chúng một cách hợp lý trong các lời nguyện và phép thuật của họ.

Với trí tuệ và sức mạnh của mình, ba phù thủy đã lập ra một bảng ghi chép tỉ mỉ từng bộ ba số nguyên dương, đảm bảo rằng không có bộ ba số nào vượt quá giới hạn được chỉ định. Bảng ghi chép này đã trở thành một tài liệu quý giá, truyền lại qua nhiều thế hệ để làng luôn có thể tận dụng sức mạnh của phép thuật này.

Với tinh thần khám phá và sự kỳ vọng vào sức mạnh của bảng ghi chép, người dân làng đều tìm kiếm và áp dụng những bộ ba số này vào cuộc sống hàng ngày. Từ việc trồng trọt, xây dựng nhà cửa cho đến cầu nguyện và lời cầu xin, mọi người đều tin rằng sức mạnh của ba phù thủy sẽ mang lại niềm vui và may mắn cho họ.

Nhiệm vụ của bạn là tiếp tục truyền thuyết này, giúp đếm và in ra tất cả các bộ ba số nguyên dương sao cho tích của ba số đó không vượt quá \(N\) và chúng được sắp xếp tăng dần, để tiếp tục lan tỏa sức mạnh kỳ diệu của phép thuật này đến với mọi người trong làng LQDOJ này.

Input

• Chứa số nguyên dương duy nhất \(N\) \((1 \le N \le 10^{11})\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): Có \(N \le 200\).
• Subtask \(2\) (\(25\%\) số điểm): Có \(N \le 1500\).
• Subtask \(3\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

7

9

shiba quyết định chơi một trò chơi có độ khó cao. Trong trò chơi, có tất cả \(n\) cửa, cửa thứ \(i\) nếu thắng sẽ được thưởng một lượng điểm đúng bằng \(i\), ngược lại nếu thua sẽ bị trừ một lượng điểm đúng bằng \(i\). Trò chơi được thiết kế bởi _minhduc, mà cậu ấy bị ám ảnh với các số \(2\) nên các cửa là luỹ thừa của \(2\) thì sẽ được giảm độ khó.

Do kĩ năng chơi không quả hay của mình, shiba chỉ có thể thắng được các cửa được giảm độ khó. Hỏi số điểm shiba nhận được sau khi chơi đủ \(n\) trò chơi là bao nhiêu?

Input

• Dòng thứ nhất chứa một số nguyên dương \(T\) (\(T \le 10^3\)) - số lượng bộ test.
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(n\) (\(n \le 10^8\)).

Output

• Gồm \(T\) dòng, mỗi dòng là một số nguyên là kết quả của bộ test đó.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 10^3\).
• Subtask \(2\) (\(70\%\) số điểm): không có ràng buộc gì thêm.

Example

2
1
4

1
4

Dãy số gồm \(N\) số nguyên dương \(a_1,a_2,a_3,\ldots,a_N\) (thỏa mãn \(a_1 \le a_2 \le ... \le a_N\)) được gọi là một dãy chia hết nếu phần tử trong mảng là ước của phần tử kế tiếp, tức là \(a_i\vdots\ a_{i-1}\) với mọi \(1 \le i < N\).

Yêu cầu: Cho hai số nguyên dương \(N\) và \(K\), tìm số dãy chia hết có độ dài là \(K\). Biết rằng các số trong dãy không vượt quá \(N\).

Input

• Chứa hai số nguyên dương \(N\) và \(K\) \((1 \le N,K \le 2000)\).

Output

• In ra kết quả bài toán sau khi chia lấy dư cho \(10^9+7\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): Có \(K = 2\).
• Subtask \(2\) (\(25\%\) số điểm): Có \(K = 3\).
• Subtask \(3\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 2

5

Vào các ngày cuối tuần, shiba sẽ dành thời gian ngồi xem phim cùng với người yêu của mình.

Người yêu của shiba đã quyết định sẽ xem một danh sách các bộ phim gồm \(n\) bộ phim, bộ phím thứ \(i\) có thời lượng là \(a_i\) phút. Tuy nhiên, việc xem phim lâu dễ gây ra nhàm chán. Chính vì thế, shiba mới quyết định "bật nóc", đổi một vài bộ phim theo ý của mình.

Phim không nhàm chán, nhưng thời lượng phim thì rất nhàm chán. Một dãy các bộ phim liên tiếp được gọi là nhàm chán nếu như ước chung lớn nhất của thời lượng các bộ phim đó bằng đúng số lượng bộ phim trong dãy đó. Nói cách khác, một dãy các bộ phim liên tiếp từ \(l\) đến \(r\) được gọi là nhám chán nếu \(gcd(a_l, a_{l+1}, a_{l+2},..., a_{r}) = r - l +1\). Để bớt nhàm chán, shiba có quyền đổi thời lượng của một bộ phim bất kì thành một bộ phim khác có thời lượng bất kì. Nói cách khác, shiba được quyền chọn bộ phim thứ \(i\) và một bộ phim khác có thời lượng là \(t\), sau đó gán cho bộ phim thứ \(i\) có thời lượng là \(t\). Việc thực hiện thay đổi bộ phim ở tuần thứ \(x\) chỉ có tác dụng ở tuần đó, các tuần khác không bị ảnh hưởng.

Việc xem phim được chia làm \(n\) tuần. Vào tuần thứ nhất, shiba sẽ xem \(1\) bộ phim, là bộ phim có thời lượng \(a_1\). Vào tuần thứ hai, shiba sẽ xem \(2\) bộ phim, là các bộ phim có thời lượng \(a_1, a_2\). Cứ như vậy, vào tuần thứ \(k\), shiba sẽ xem \(k\) bộ phim, là các bộ phim có thời lượng \(a_1, a_2,..., a_k\).

Yêu cầu: Hỏi với mỗi tuần, shiba phải thay đổi ít nhất bao nhiêu bộ phim để danh sách phim của cậu ấy không bị nhàm chán?

Input

• Dòng thứ nhất chứa một số nguyên dương \(n\) (\(n \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2,... a_n\) (\(a_i \le 10^9\)).

Output

• Gồm một dòng chứa \(n\) số nguyên, số nguyên thứ \(i\) là số lượng bộ phim phải đổi ít nhất trong tuần thứ \(i\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 10^3\).
• Subtask \(3\) (\(60\%\) số điểm): không có giới hạn gì thêm.

Example

1
1

1

Vào kỳ nghỉ Chủ Nhật, _minhduc đã cùng các bạn đi dạo chơi quanh phố. Khi đi ngang qua khu vui chơi, thì bất chợt có một tờ giấy bay qua, và bay đúng vào mặt của _minhduc. Tờ giấy đó là nội dung của trò chơi có thưởng của tay code số một server LQDOJ, kèm theo đó là một bài toán như sau:

Cho \(N\) địa điểm và \(N – 1\) con đường hai chiều nối trực tiếp giữa hai địa điểm, đảm bảo rằng giữa hai địa điểm bất kỳ chỉ có duy nhất một đường đi.

Mỗi địa điểm \(i\) sẽ có một biểu tượng mang con số là \(A_i\). Ta định nghĩa \(F_{u,v}\) là số các biểu tượng khác nhau của các địa điểm trên đường đi từ \(u\) tới \(v\). Và \(S_u\) là tổng tất cả các \(F_{u,v}\) với mọi \(v \in [1;N]\).

Yêu cầu của trò chơi là đưa ra tất cả kết quả \(S_u\) với \(u \in [1;N]\). Giải được trò chơi này sẽ được một vé đi xem phim "Đất rừng phương Nam" miễn phí.

Vì trước giờ là thành viên trong đội tuyển quốc gia, với lại đây là trò chơi tay code số một server LQDOJ mà lâu nay ngưỡng mộ, nên _minhduc muốn ra tay với bài toán trong trò chơi này để giành lấy vé xem phim ấy. Nhưng khổ nỗi là _minhduc đã quên mang Macbook M2 Pro của anh ta đi, với lại không muốn chịu thua, nên các bạn hãy giúp _minhduc có đáp án nhé.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\). \((1 \le N \le 10^5)\).
• Dòng tiếp theo chứa \(N\) số nguyên dương \(A_1,A_2,...,A_N\) \((1 \le A_i \le 10^5)\)
• \(N-1\) dòng còn lại, mỗi dòng mỗi dòng chứa cặp số nguyên dương \(u,v\) thể hiện có con đường nối trực tiếp giữa hai địa điểm \(u,v\) \((1 \le u,v \le N,u \neq v)\).

Output

• Gồm \(N\) dòng, dòng thứ \(u\) chứa số nguyên dương duy nhất \(S_u\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): Có \(N \le 200\).
• Subtask \(2\) (\(30\%\) số điểm): Có \(N \le 2000\).
• Subtask \(3\) (\(10\%\) số điểm): Có các địa điểm nối với nhau theo một đường thẳng.
• Subtask \(4\) (\(10\%\) số điểm): Có các số \(A_i\) đôi một phân biệt.
• Subtask \(5\) (\(10\%\) số điểm): Có \(A_i \le 10\).
• Subtask \(6\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

5 
3 7 7 5 4 
1 2 
2 3 
2 5 
2 4

11
8
8
11
11