Số chính phương (DHBB CT)

Tác giả:

Dạng bài

Điểm: 1700 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Bình là một cậu bé rất đam mê toán học, đặt biệt là phần số học. Giải các bài toán về số nguyên tố, số chính phương, chia hết, \(\ldots\) là sở trường của Bình. Nhân dịp Kỳ thi Duyên hải năm nay được tổ chức lần dầu tiên theo hình thức thi online, Bình gửi đến các bạn một bài toán liên quan đến số chính phương.

Với số tự nhiên \(n\) cho trước, Bình yêu cầu bạn đếm số bộ ba số nguyên \((a,b,c)\) với \((1 \leq a<b<c \leq n)\) sao cho tất cả các tích \(a×b,a×c\) và \(b×c\) đều là các số chính phương.

Input

Duy nhất số nguyên dương n \((n \leq 5 * 10 ^ 6)\)

Output

Ghi ra số lượng bộ 3 số \(a,b,c\) tìm được.

Scoring

Subtask \(1\) (\(24\%\) số điểm): \(1 \leq n \leq 100\)
Subtask \(2\) (\(20\%\) số điểm): \(100 < n \leq 5000\)
Subtask \(3\) (\(28\%\) số điểm): \(5000 < n \leq 10 ^ 5\)
Subtask \(4\) (\(28\%\) số điểm): \(10 ^ 5 < n \leq 5 * 10 ^ 6\)

Example

Test 1

Input

Output

Note

Với \(n=20\) có tất cả \(5\) bộ là: \((1,4,9);(1,4,16);(1,9,16);(4,9,16)\) và \((2,8,18)\).

Bình luận

`Spoiler Alert`

Hint 0

Giải theo hướng toán học và cải tiến dần

Hint 1

Phân tích dưới dạng thừa số nguyên tố để tìm quy luật

Khi phân tích các số a, b, c về dạng \(p_1 ^{f_1} * p_2 ^{f_2} * ... * p_k ^{f_k}\) với \(p_i\) nguyên tố phân biệt, \(k_i\) số mũ dương

Thì tích của một cặp bất kì là số chính phương <=> các số mũ \(f_1, f_2, ..., f_k\) đều phải cùng chẵn hoặc cùng lẻ

Hint 2

Ta chỉ quan tâm chẵn lẻ, nên có thể lấy các số mũ modulo cho 2

Giả sử có \(x = p_1 ^{f_1} * p_2 ^{f_2} * ... * p_k ^{f_k}\)

Gọi \(mask(x) = p_1 ^{f_1 \% 2} * p_2 ^{f_2 \% 2} * ... * p_k ^{f_k \% 2}\)

Khi đó ta có \(mask(x)\) là số nguyên dương nhỏ nhất để \(mask(x) * x\) là số chính phương

Hint 3

Duyệt \(a = 1 -> n\)

Gọi \(f\) là số lượng số \(j \leq i\) thỏa mãn \(mask(j) = mask(i)\)

Tại mỗi vị trí \(i\) có \(f * (f - 1) / 2\) cách chọn 2 số \(b, c\) còn lại thỏa điều kiện đề bài

Reference AC code | \(O(n)\) time | \(O(n)\) auxiliary space | Online Solving, Factorization, Sieving, Math, DP_count

C++

vector<int> prime; /// prime list
vector<int> lpf;   /// Lowest prime factor, lpf[x] is smallest prime divisor of x
void sieve(int lim = LIM) /// O(n)
{
    prime.assign(1, 2);
    lpf.assign(lim + 1, 2);

    lpf[1] = 1; /// For easier calculation but can cause inf loops
    for (int i = 3; i <= lim; i += 2) {
        if (lpf[i] == 2) prime.push_back(lpf[i] = i);
        for (int j = 0; j < sz(prime) && prime[j] <= lpf[i] && prime[j] * i <= lim; ++j)
            lpf[prime[j] * i] = prime[j];
    }
}

/// mask(x) is smallest positive number that mask(x) * x is a perfect square
int getMask(int x) /// O(log n)
{
    int mask = 1;
    while (x > 1) {
        int p = lpf[x], f = 0;
        do x /= p, f++; while (p == lpf[x]);
        if (f & 1) mask *= p; /// if current power is odd, we mutiple mask with current prime
    }
    return mask;
}

/// nC2 = number of ways to choose another 2 numbers
ll f(int x) { return 1LL * x * (x - 1) / 2; }
ll magic(int n) /// O(n)
{
    vector<int> c(n + 1, 0); /// Save the frequency of each mask
    ll res = 0;
    for (int a = 1; a <= n; ++a) /// Check all cases of a
        res += f(c[getMask(a)]++);

    return res;
}

int main() /// O(n)
{
    int n = readInt();
    sieve(n + 500);
    cout << magic(n);    
    return 0;
}

2 bình luận nữa