Đếm cặp số tạo thành số chính phương

[phyzicc (Nguyen Chien)]

Em đang gặp vấn đề về một bài tập nhỏ, cụ thể là tạo một hàm để đếm các cặp số nguyên dương từ một tập hợp các số nguyên dương không lớn hơn số nguyên N sao cho tích của chúng tạo ra một số chính phương.

Em đã làm và kết quả đúng nhưng chưa được tối ưu và đã thử tìm nhiều cách nhưng không hiệu quả.

Em mong mọi người có thể giúp em. Code của em ở đây

Input : Một dòng chứa số nguyên dương N (1 <= N <= 100.000)

Output : Số cặp tạo thành số chính phương. Ví dụ với N = 4 thì có 6 cặp số với mỗi số nhỏ với mỗi số nhỏ hơn 4 nhưng tích là số chính phương đó là (1, 1), (1, 4), (4, 1), (2, 2), (3, 3), (4, 4).

#include <iostream>
#include <math.h>
using namespace std;
bool CheckSquareNum(int n){
    int sqr = sqrt(n);
    return (sqr * sqr == n);
}
int Chinhphuong(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++){
        for (int j = i + 1; j <= n; j++) {
            if (CheckSquareNum(i * j))
                count++;
        }
    }
    return count * 2 + n;
}
int main() {
    int n;
    cin >> n;
    cout << Chinhphuong(n);
    return 0;
}

[nguy4nkjn (Nguyen Khasnh)]

Vì đề bài yêu cầu số nguyên dương <= N nào đó nên thay vì lặp tất cả các số để kiểm tra xem nó có phải là số chính phương không thì bạn có thể tự tạo số chính phương (đơn giản là bình phương thôi). Chắc chắn bạn sẽ có được số chính phương <= N và bỏ qua những số không phải.
Đoạn code ví dụ chỉ in ra số chính phương không vượt qua n:

cin >> n;
for (int i = 1; i*i <= n; i++){
    cout << i*i << "\n";
}

[anonymous277]

Nếu đã gọi là không tối ưu, thì bạn có biết độ phức tạp của giải thuật bạn đang dùng là gì không?
Bạn mong muốn chạy với đầu vào khoảng bao nhiêu, và độ phức tạp bạn mong đợi sẽ là gì?
Bạn có thấy bước nào bị lặp lại nhiều lần không cần thiết để tối ưu nó chưa?

Sau khi trả lời các câu này, mình nghĩ sẽ có nhiều người support bạn hơn đó

[phyzicc (Nguyen Chien)]

Em đã bổ sung rồi ạ, cảm ơn anh

[anonymous277]

Dường như bạn không hiểu các câu hỏi bên trên cho lắm, đặc biệt là phần độ phức tạp của thuật toán. Nếu đúng vậy thì thảo luận đến việc tối ưu là không cần thiết và sẽ không có tác dụng chi đâu bạn à.

[nguy4nkjn (Nguyen Khasnh)]

Nếu là như code bạn viết thì thuật toán sẽ có đội phức tạp là O(n^2) còn của mình đưa ra thì sẽ chỉ còn O(n) thôi (đương nhiên nếu có thể có thuật toán nào đó tốt hơn)

[phyzicc (Nguyen Chien)]

Em có thể tham khảo code của anh không, bài này em đã hoàn thành rồi. Code của em ở đây, độ phức tạp là O(n√n)

int Chinhphuong(int n)
{
    int squarefree[n + 1];
    for (int k = 0; k <= n; k++)
        squarefree[k] = k;
    int res = 0;
    for (int i = 1; i <= n; ++i)
        if (squarefree[i])
        {
            for (int j = 1; i * j * j <= n; ++j)
            {
                squarefree[i * j * j] = 0;
                res += j - 1;
            }
        }

    return res * 2 + n;
}