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

Xem PDF

Đ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\)\(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
20 
Output
5
Note

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


Bình luận


  • 13
    SPyofgame    3:36 p.m. 13 Tháng 6, 2020 chỉnh sửa 2

    Spoiler Alert


    Hint 0

    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\)\(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