The Digit GCD Array
UptoSkills Arena is organizing a coding contest where participants submit their solutions. Each submission has a unique ID, which is a positive integer. The contest organizers want to analyze the relationship between the submission IDs based on the greatest common divisor (GCD) of the sum of their digits. They are interested in pairs of distinct submissions whose IDs have a sum of digits that share a common factor greater than 1.
Given an array of submission IDs, find the number of distinct pairs of indices (i, j) such that i < j and the greatest common divisor of the sum of digits of A[i] and the sum of digits of A[j] is greater than 1.
Input
The first line contains an integer n, the number of submissions. The next line contains n space-separated integers A_1, A_2, ..., A_n representing the submission IDs.
Output
Print a single integer, the total count of pairs (i, j) with i < j such that gcd(sum_of_digits(A[i]), sum_of_digits(A[j])) > 1.
Constraints
1 <= n <= 200000 1 <= A_i <= 10^9
Example 1
5 12 34 56 78 90
3
Sums of digits are: 3, 7, 11, 15, 9. Pairs with GCD > 1: (3, 9) gcd=3, (15, 9) gcd=3. Total = 2.
Example 2
4 2 4 6 8
6
Sums of digits are: 2, 4, 6, 8. All pairs have GCD > 1. Total = 6.
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 34 56 78 90
4 2 4 6 8