Rafid's club is analyzing a dataset and wants to count exactly how many PAIRS of numbers in it have a GCD equal to a specific target value. Given N and an integer array of size N, and an integer G, count the number of pairs (i,j), i<j, such that gcd(a_i,a_j) = G exactly. Use a divisor-based counting technique (count multiples of each d, apply inclusion-exclusion / Möbius-style subtraction from large d to small d) rather than checking all O(N^2) pairs.
Input
Line1: N G. Line2: N integers.
Output
Count of pairs with gcd exactly G.
Constraints
1 ≤ N ≤ 10^5, 1 ≤ a_i ≤ 10^5
Sample Input
4 2 2 4 6 3
Sample Output
2
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.