A Boring Problem


Submit solution

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

Given two integers A and B, output the sum of all the common factors of A and B that are not prime.

Constraints

For 20% of the points, 1 \le A, B \le 50. These constraints were arbitrarily chosen for a brute force subtask.

For the remaining 80%, 1 \le A, B \le 10^{18}.

Sample Input 1

28 14

Sample Output 1

15

Explanation for Sample 1

Factors of 28 are 1, 2, 4, 7, 14, 28. Factors of 14 are 1, 2, 7, 14.

1, 2, 7, 14 are the common factors, but 2 and 7 are prime numbers so we exclude them.

Adding up the rest, we get 1+14 = 15.

Sample Input 2

27 36

Sample Output 2

10

Explanation for Sample 2

Factors of 27 are 1, 3, 9, 27. Factors of 36 are 1, 2, 3, 4, 6, 9, 12, 18, 36.

1, 3, 9 are the common factors, but, 3 is a prime number so we exclude it.

Adding up the rest, we get 1+9 = 10.


Comments

There are no comments at the moment.