5412 : C13 - 두 카드 선택 (Select 2)
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$ 장의 카드가 있으며 각각 정수 $A_1, A_2, \dots, A_N$ 이 적혀 있습니다.
서로 다른 두 장의 카드 $(i, j)$ ($1 \le i < j \le N$)를 선택하는 방법 중에서 다음 조건을 만족하는 경우의 수를 구하는 프로그램을 작성하십시오.
• 조건: 두 카드에 적힌 수의 곱을 $10^9 + 7$ 로 나눈 나머지가 $P$ 가 된다. 즉, $(A_i \times A_j) \bmod (10^9 + 7) = P$.
[제약 조건]
• $2 \le N \le 100{,}000$
• $0 \le P < 10^9 + 7$
• $0 \le A_i < 10^9 + 7$
• 입력되는 모든 값은 정수입니다.
서로 다른 두 장의 카드 $(i, j)$ ($1 \le i < j \le N$)를 선택하는 방법 중에서 다음 조건을 만족하는 경우의 수를 구하는 프로그램을 작성하십시오.
• 조건: 두 카드에 적힌 수의 곱을 $10^9 + 7$ 로 나눈 나머지가 $P$ 가 된다. 즉, $(A_i \times A_j) \bmod (10^9 + 7) = P$.
[제약 조건]
• $2 \le N \le 100{,}000$
• $0 \le P < 10^9 + 7$
• $0 \le A_i < 10^9 + 7$
• 입력되는 모든 값은 정수입니다.
입력 설명
첫째 줄에 정수 $N$ 과 $P$ 가 공백으로 구분되어 주어집니다.
둘째 줄에 각 카드에 적힌 정수 $A_1, A_2, \dots, A_N$ 이 공백으로 구분되어 주어집니다.
둘째 줄에 각 카드에 적힌 정수 $A_1, A_2, \dots, A_N$ 이 공백으로 구분되어 주어집니다.
출력 설명
조건을 만족하는 두 카드의 조합 수를 출력하십시오.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 6
1 2 3 6
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
$(A_1, A_4) = (1, 6) \implies 1 \times 6 = 6$, $(A_2, A_3) = (2, 3) \implies 2 \times 3 = 6$ 의 $2$ 가지 조합이 조건을 만족합니다.