Bài tập

Định nghĩa cây

Một cây là một đồ thị vô hướng liên thông không chứa chu trình. Tức là, cây là một đồ thị \(G = (V, E)\) thỏa mãn các điều kiện sau:

• \(G\) liên thông, tức là luôn có đường đi giữa hai đỉnh bất kỳ.
• \(G\) không chứa chu trình, tức là không có tập con của các cạnh tạo thành một đường khép kín.

Tính chất của cây

Một cây với \(n\) đỉnh (\(n \geq 1\)) có các tính chất sau:

• Cây có đúng \(n-1\) cạnh.
• Giữa hai đỉnh bất kỳ trong cây luôn tồn tại duy nhất một đường đi.
• Thêm một cạnh bất kỳ vào cây sẽ tạo thành đúng một chu trình.
• Loại bỏ một cạnh bất kỳ khỏi cây sẽ làm đồ thị không còn liên thông.

Ứng dụng của cây

Cây có nhiều ứng dụng quan trọng trong tin học và toán học:

• Cấu trúc dữ liệu: Cây nhị phân tìm kiếm, cây AVL, cây đỏ-đen.
• Mạng máy tính: Mô hình phân cấp mạng.
• Hệ thống tệp: Cấu trúc thư mục trong hệ điều hành.
• Nén dữ liệu: Cây Huffman.

Bài toán

Cho đồ thị có dạng một cây có \(n\) đỉnh có gốc của cây là đỉnh \(1\). Hãy trả lời các câu hỏi sau :

• Câu hỏi \(1\) : Với mỗi \(x\) từ \(1\) đến \(n\), hãy in ra cha của \(x\) trên cây. Nếu \(x\) là gốc của cây thì in ra chính nó.
• Câu hỏi \(2\) : Tìm khoảng cách từ gốc của cây đến tất cả các đỉnh trên cây.
• Câu hỏi \(3\) : In ra tất cả các đỉnh lá của cây (theo thứ tự tăng dần chỉ số).
• Câu hỏi \(4\) : Với mỗi \(x\) từ \(1\) đến \(n\), hãy in ra số lượng đỉnh trong cây con gốc \(x\).

Input

Dòng đầu tiên là hai số nguyên dương \(n\) và \(t\). \(n\) là số đỉnh của cây và \(t\) là chỉ số câu hỏi. \((1 \leq n \leq 500, 1 \leq t \leq 4)\).

\(n - 1\) dòng tiếp theo, mỗi dòng là hai số nguyên dương \(u\) và \(v\), là cạnh của cây.

Output

Với câu hỏi in ra tương ứng, xem test ví dụ để hiểu rõ hơn.

Example

5 1
1 2
1 3
2 4
2 5

1 1 1 2 2 

5 2
1 2
1 3
2 4
2 5

0 1 1 2 2 

5 3
1 2
1 3
2 4
2 5

3 4 5 

5 4
1 2
1 3
2 4
2 5

5 3 1 1 1 

Cho số nguyên dương \(N\) và hai số nguyên tố \(A, B\).
Hỏi có bao nhiêu số không lớn hơn \(N\) chỉ chia hết cho \(A\) hoặc \(B\)?

Input

Vào từ tệp văn bản CHIAHET.INP gồm:

• Dòng 1 ghi số nguyên dương \(N\);
• Dòng 2 ghi 2 số nguyên tố \(A, B\).

Output

Ghi ra tệp văn bản CHIAHET.OUT một số là kết quả của bài toán.

Example

10
2 3

6

Scoring

• Subtask 1: Có 36 test (90%) tương ứng 5,4 điểm với \(N \le 10^6\), \(A, B < N\);
• Subtask 2: Có 4 test (10%) tương ứng 0,6 điểm với \(10^6 < N \le 10^9\), \(A, B < N\).

Trong giờ hình học, An được thầy giáo dạy về công thức tính diện tích của hình chữ nhật và hình vuông. An thấy hình vuông rất đẹp nên cậu định nghĩa một hình chữ nhật "đẹp" là hình chữ nhật có các đặc điểm sau:

• Độ dài hai cạnh là các số nguyên dương.
• Diện tích bằng diện tích của một hình vuông có độ dài cạnh là một số nguyên dương.

An đã phát biểu định nghĩa này trước lớp và thách đố bài toán như sau:

Cho số nguyên dương \(x\). Tìm số nguyên dương \(y\) nhỏ nhất để \(x\) và \(y\) là độ dài hai cạnh của một hình chữ nhật "đẹp".

Yêu cầu
Giúp cả lớp tìm số nguyên dương \(y\) thỏa mãn bài toán của An.

Input

Nhập từ tệp văn bản B1.INP, gồm một dòng duy nhất chứa số nguyên dương \(x\).

Output

Ghi ra tệp văn bản B1.OUT, gồm một dòng duy nhất chứa số nguyên dương \(y\).

Example

4

1

6

6

8

2

Scoring

• \(90\%\) số test thỏa mãn \(1 \le x \le 10^6\).
• \(10\%\) số test thỏa mãn \(10^6 < x \le 10^{12}\).

Bờm tham gia trò chơi rút thăm trúng thưởng trong đêm hội Trăng rằm. Ban tổ chức chuẩn bị \(k\) loại thẻ bài, các loại thẻ bài tương ứng ghi các giá trị từ \(1\) đến \(k\), các thẻ được sắp xếp vào trong \(2\) chiếc hộp như sau:

• Hộp thứ nhất: chỉ chứa các loại thẻ bài có giá trị là số lẻ trong khoảng từ \(1\) tới \(k\), số lượng mỗi loại thẻ không giới hạn.
• Hộp thứ hai: chỉ chứa các loại thẻ bài có giá trị là số chẵn trong khoảng từ \(1\) tới \(k\), số lượng mỗi loại thẻ không giới hạn.

Theo thể lệ của Ban tổ chức, một người chơi sẽ được thực hiện \(n\) lần rút thẻ. Các lượt rút thẻ theo thứ tự bắt đầu từ hộp thứ nhất tới hộp thứ hai và lặp lại quá trình đó.

Ví dụ: \(k = 4, n = 3\)

• Lượt thứ nhất: Người chơi rút thẻ trong hộp thứ nhất có thể nhận được các thẻ bài có giá trị \(1\) hoặc \(3\).
• Lượt thứ hai: Người chơi rút thẻ trong hộp thứ hai có thể nhận được các thẻ bài có giá trị \(2\) hoặc \(4\).
• Lượt thứ ba: Người chơi rút thẻ trong hộp thứ nhất có thể nhận được các thẻ bài có giá trị \(1\) hoặc \(3\).

Ban tổ chức đưa ra một con số \(m\) và người chơi sẽ nhận được quà nếu tổng số thẻ sau \(n\) lần rút là một số chia hết cho \(m\).

Yêu cầu: Hãy tính giúp Bờm xem có bao nhiêu cách rút ra các thẻ bài để có thể nhận được thưởng.

Input

Một dòng chứa ba số nguyên dương \(n, k, m\) \((2 \le n, k \le 10^9, m \le 100)\).

Output

Ghi ra một số nguyên dương là số cách rút thẻ thỏa mãn yêu cầu của Ban tổ chức. Vì kết quả rất lớn nên chỉ cần đưa ra phần dư của đáp án khi chia cho \(123456789\).

Example

3 4 4

4

3 2 4

1

Scoring

• Subtask 1 (20%): \(n, k \leq 1000\).
• Subtask 2 (30%): \(m\) lẻ, \(n \leq 10^3\).
• Subtask 3 (30%): \(n \leq 10^3\).
• Subtask 4 (20%): Không có ràng buộc gì thêm.