Count Pairs with Equal Digit GCD
Given an array of N positive integers, count the number of pairs (i, j) such that i < j and the greatest common divisor (GCD) of the digits of A[i] is equal to the GCD of the digits of A[j]. The GCD of a single digit is the digit itself. For a number with multiple digits, calculate the GCD of all its digits. For example, GCD(1, 2, 3) = 1, GCD(2, 4, 8) = 2, GCD(5) = 5.
Input
The first line contains an integer N. The second line contains N space-separated positive integers A[1], A[2], ..., A[N].
Output
Print a single integer, the total count of such pairs.
Constraints
1 <= N <= 200000, 1 <= A[i] <= 10^9
Example 1
5 12 24 36 48 15
1
Pairs are (12, 24), (12, 36), (12, 48), (24, 36), (24, 48), (36, 48) because gcd(1,2)=1, gcd(2,4)=2, gcd(3,6)=3, gcd(4,8)=4, gcd(1,5)=1. The digit GCDs are 1, 2, 3, 4, 1. Counts: {1: 2, 2: 1, 3: 1, 4: 1}. Pairs from GCD=1: 2*(2-1)/2 = 1. Total pairs = 1.
Example 2
6 6 66 18 27 9 99
3
Digit GCDs: gcd(6)=6, gcd(6,6)=6, gcd(1,8)=1, gcd(2,7)=1, gcd(9)=9, gcd(9,9)=9. Counts: {6: 2, 1: 2, 9: 2}. Pairs from GCD=6: 1. Pairs from GCD=1: 1. Pairs from GCD=9: 1. Total pairs = 1 + 1 + 1 = 3.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 12 24 36 48 15
6 6 66 18 27 9 99