BỘ HAI SỐ

Xem PDF

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

Cho \(N\) số nguyên dương \(a_1,a_2,...,a_N\) và một số nguyên dương \(M\). Hãy đếm số bộ hai số \(i,j\) sao cho:

  • \(1 \leq i \leq j \leq N\)
  • \(a_i \times a_j\) chia hết cho \(M\)

INPUT

  • Dòng đầu tiên chứa \(2\) số nguyên dương \(N\)\(M\) \((3 \leq N \leq 10^6, 1 \leq M \leq 10^3)\).
  • Dòng thứ hai chứa \(N\) số nguyên dương \(a_1,a_2,...,a_N\) \((0 \leq a_i \leq 10^9 )\)

OUTPUT

  • In ra một số nguyên duy nhất là số lượng bộ \(2\) chỉ số \((i,j)\) thỏa mãn yêu cầu đề bài.

Example

Test 1

Input
4 6
2 3 3 12
Output
6
Note

Ta có \(6\) cặp thỏa mãn: \((a_1,a_2);(a_1,a_3);(a_1,a_4);(a_2,a_4);(a_3,a_4);(a_4,a_4)\);

Ràng buộc

  • Subtask \(1\) (\(20\%\) số test): Có \(3 \leq N \leq 10^3\).
  • Subtask \(2\) (\(80\%\) số test): Không có ràng buộc gì thêm.

Bình luận

  • buianhnhat2011 7:42 a.m. 14 Tháng 2, 2025

    include<bits/stdc++.h>

    using namespace std;
    unsigned long long n,i,a[10000009],b[10000009],m,t;
    int main()
    {

    cin >>n>>m;
    for(i=1;i<=n;i++) cin >>a[i];
    fill(b+1,b+n,1);
    b[a[1]]++;
    for(i=2;i<=n;i++)
    {
        if(a[i]%m!=0)
        {
            b[a[i]%m]=b[a[i]%m]+1;
            a[i]=a[i]%m;
            if((double)m/a[i]==(unsigned long long) m/a[i])
            {
                t=t+b[m/a[i]];
            }
        }
        else
        {
            t=t+i;
        }
    }
    cout <<t;
    

    }
    sao code này lỗi v nhỉ