BỘ HAI SỐ

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Tác giả:

khanhho

Dạng bài

Đ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\) và \(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

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

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ỉ

Phản hồi