2025 THT bảng B - Buổi 13

Số tự nhiên \(y\) được gọi là một ước thực sự của số tự nhiên \(x\) nếu \(x\) chia hết cho \(y\) và \(x>y\).

Yêu cầu: Nhập vào từ bàn phím một số nguyên dương \(x\) (với \(x > 1\)), hãy tìm và in ra màn hình số \(y\) là ước thực sự lớn nhất của số \(x\).

Input: Một số nguyên dương \(x\)

Output: Ghi ra số nguyên \(m\) thỏa mãn yêu cầu của đề bài.

Scoring

• Có 70% test tương ứng với \(x ≤ 10^6\).
• Có 20% test tương ứng với \(x ≤ 10^8\).
• Có 10% test tương ứng với \(x ≤ 10^{10}\).

Example

10

5

Yêu cầu: Nhập từ bàn phím một xâu kí tự \(S\). Hãy đếm và in ra màn hình số lượng kí tự xuất hiện ít nhất 2 lần trong xâu kí tự \(S\) (có phân biệt chữ hoa và chữ thường).

Scoring

• Xâu S có không quá 255 kí tự.

Example

abcbMbdmccccd

3

Một số được gọi là số nguyên tố đối xứng nếu nó là một số nguyên tố và khi đọc số này từ trái sang phải hay từ phải sang trái đều như nhau. Chẳng hạn số 131 là số nguyên tố đối xứng.

Yêu cầu: Cho trước một số nguyên dương \(x\). Hãy tính xem có bao nhiêu số nguyên tố đối xứng lớn hơn 10 và bé hơn \(X\).

Input: Đọc ở file văn bản NTDX.INP một số nguyên dương \(x\)

Output: Ghi ra file văn bản NTDX.OUT số nguyên \(m\) thỏa mãn yêu cầu của đề bài.

Scoring

• Có 50% test tương ứng với \(x ≤ 10^4\).
• Có 30% test tương ứng với \(x ≤ 10^6\).
• Có 20% test tương ứng với \(x ≤ 10^{10}\).

Example

150

3

Cho trước một số tự nhiên \(x\) có \(n\) chữ số và không có 2 chữ số nào giống nhau. Người ta thay đổi trật tự các chữ số của số \(x\) cho nhau để được số tự nhiên mới cũng có \(n\) chữ số và mỗi số mới này được gọi là một hoán vị của số \(x\).

Yêu cầu: Tính tổng của số \(x\) và tất cả các hoán vị của \(x\).

Input: Đọc ở file văn bản THV.INP một số nguyên dương \(x\)

Output: Ghi ra file văn bản THV.OUT số nguyên \(m\) thỏa mãn yêu cầu của đề bài.

Scoring

• Có 30% test tương ứng với \(x ≤ 10^3\).
• Có 20% test tương ứng với \(x ≤ 10^5\).
• Có 30% test tương ứng với \(x ≤ 10^{8}\).
• Có 20% test tương ứng với \(x ≤ 10^{10}\).

Example

123

1332

Cho \(n\) số tự nhiên \({1,2,3,4, ..., n}\). Tổ hợp chập \(k\) của \(n\) số này là một cách chọn ra \(k\) số khác nhau trong \(n\) số, không kể thứ tự (tức là: chọn \([1,2,3]\) cũng giống như chọn \([3,2,1], [2,3,1], [1,3,2], ...\)).

Cho biết trước \(n,k\). Em hãy in ra tất cả tổ hợp chập \(k\) của \(n\) theo thứ tự từ điển.

Nhắc lại, hai dãy số \(s,t\) có cùng độ dài \(k, s\) có thứ tự từ điển bé hơn \(t\) khi tồn tại duy nhất \(i (1 \le i \le k)\)

• \(s[j] = t[j]\) với mọi \(1 \le j < i\)
• \(s[i] < t[i]\)

Nói cách khác, \(s < t\) khi tại vị trí \(i\) đầu tiên mà \(s[i] \neq t[i]\), ta có \(s[i] < t[i]\).

Trong tất cả các tổ hợp (cách chọn), có bao nhiêu cách mà tích của các số được chọn là một số chính phương?

Input

• Một dòng duy nhất chứa hai số \(n,k (1 \le k \le n \le 16)\)

Output

• In ra các tổ hợp, mỗi cách trên một dòng
• Ở dòng cuối cùng, in ra số lượng tích là số chính phương

Example

5 3 

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
0