LÝ THUYẾT SỐ CHÍNH PHƯƠNG

Danh sách bài

Bài 1. SQCHECK - Kiểm tra số chính phương

Đề bài. Cho số nguyên dương n. Hãy kiểm tra n có phải là số chính phương hay không. Gợi ý. Một số là số chính phương nếu tồn tại số nguyên k sao cho n = k^2. Dữ liệu vào. Input gồm một số nguyên n. Dữ liệu ra. In YES nếu n là số chính phương, ngược lại in NO. Ràng buộc theo subtask.

• Sub 1: 1 <= n <= 10^6
• Sub 2: 1 <= n <= 10^12
• Sub 3: 1 <= n <= 10^18 Ví dụ.

Input
49
Output
YES

Bài 2. MINSQSUM - Tổng ít nhất các số chính phương

Đề bài. Cho số nguyên dương n. Hãy biểu diễn n thành tổng của một số số chính phương. Cần tìm số lượng số hạng ít nhất. Dữ liệu vào. Input gồm một số nguyên n. Dữ liệu ra. In ra số lượng ít nhất các số chính phương có tổng bằng n. Ràng buộc theo subtask.

• Sub 1: 1 <= n <= 100
• Sub 2: 1 <= n <= 10000
• Sub 3: 1 <= n <= 10^9 Ví dụ.

Input
13
Output
2

Bài 3. SQFREECNT - Đếm số không chứa thừa số chính phương

Đề bài. Một số nguyên dương x gọi là square-free nếu không tồn tại số chính phương d^2 > 1 chia hết cho x. Cho đoạn [L, R], hãy đếm các số square-free trong đoạn. Gợi ý. Ví dụ 12 không square-free vì chia hết cho 4; số 30 là square-free. Dữ liệu vào. Input gồm hai số nguyên L, R. Dữ liệu ra. In ra số lượng số square-free trong đoạn [L, R]. Ràng buộc theo subtask.

• Sub 1: 1 <= L <= R <= 10^5
• Sub 2: 1 <= L <= R <= 10^7, R-L <= 10^5
• Sub 3: 1 <= L <= R <= 10^12, R-L <= 10^5 Ví dụ.

Input
1 10
Output
7

Bài 4. SQEQUATION - Phương trình chính phương

Đề bài. Cho hai số nguyên dương n và m. Hãy đếm số nguyên x thỏa mãn 1 <= x <= m và x^2 + n là số chính phương. Gợi ý. Bài toán có thể kiểm tra bằng căn bậc hai với m vừa phải, hoặc biến đổi y^2 - x^2 = n. Dữ liệu vào. Input gồm hai số nguyên n, m. Dữ liệu ra. In ra số lượng giá trị x thỏa mãn. Ràng buộc theo subtask.

• Sub 1: 1 <= n <= 1000, 1 <= m <= 1000
• Sub 2: 1 <= n <= 10^6, 1 <= m <= 50000
• Sub 3: 1 <= n <= 10^9, 1 <= m <= 200000 Ví dụ.

Input
15 10
Output
1

Bài 5. SQPREFIX - Hoán vị tránh tổng tiền tố chính phương

Đề bài. Cho số nguyên n. Hãy xây dựng một hoán vị p của các số 1, 2, ..., n sao cho mọi tổng tiền tố p1 + p2 + ... + pi đều không phải số chính phương. Nếu không tồn tại, in -1. Gợi ý. Nếu tổng 1+2+...+n là số chính phương thì chắc chắn không có lời giải. Dữ liệu vào. Input gồm một số nguyên n. Dữ liệu ra. In -1 nếu không có lời giải. Ngược lại in một hoán vị hợp lệ. Ràng buộc theo subtask.

• Sub 1: 1 <= n <= 10
• Sub 2: 1 <= n <= 1000
• Sub 3: 1 <= n <= 5000 Ví dụ.

Input
4
Output
2 1 3 4

Bài 6. GOODPERM - Hoán vị cộng chỉ số thành số chính phương

Đề bài. Cho số nguyên n. Hãy xây dựng một hoán vị p của các số 1, 2, ..., n sao cho với mọi vị trí i, giá trị (i - 1) + (p_i - 1) là số chính phương. Gợi ý. Dạng xây dựng tham lam từ phải sang trái theo từng đoạn có tổng chỉ số là một số chính phương. Dữ liệu vào. Input gồm một số nguyên n. Dữ liệu ra. In ra một hoán vị hợp lệ p gồm n số nguyên. Ràng buộc theo subtask.

• Sub 1: 1 <= n <= 10
• Sub 2: 1 <= n <= 1000
• Sub 3: 1 <= n <= 5000 Ví dụ.

Input
5
Output
5 4 3 2 1