CF1498A GCD Sum

The $ \text{ $ gcdSum $ } $ of a positive integer is the $ gcd $ of that integer with its sum of digits. Formally, $ \text{ $ gcdSum $ }(x) = gcd(x, \text{ sum of digits of } x) $ for a positive integer $ x $ . $ gcd(a, b) $ denotes the greatest common divisor of $ a $ and $ b $ — the largest integer $ d $ such that both integers $ a $ and $ b $ are divisible by $ d $ . For example: $ \text{ $ gcdSum $ }(762) = gcd(762, 7 + 6 + 2)=gcd(762,15) = 3 $ . Given an integer $ n $ , find the smallest integer $ x \ge n $ such that $ \text{ $ gcdSum $ }(x) > 1 $ .

N/A

N/A

Let us explain the three test cases in the sample. Test case 1: $ n = 11 $ : $ \text{ $ gcdSum $ }(11) = gcd(11, 1 + 1) = gcd(11,\ 2) = 1 $ . $ \text{ $ gcdSum $ }(12) = gcd(12, 1 + 2) = gcd(12,\ 3) = 3 $ . So the smallest number $ \ge 11 $ whose $ gcdSum $ $ > 1 $ is $ 12 $ . Test case 2: $ n = 31 $ : $ \text{ $ gcdSum $ }(31) = gcd(31, 3 + 1) = gcd(31,\ 4) = 1 $ . $ \text{ $ gcdSum $ }(32) = gcd(32, 3 + 2) = gcd(32,\ 5) = 1 $ . $ \text{ $ gcdSum $ }(33) = gcd(33, 3 + 3) = gcd(33,\ 6) = 3 $ . So the smallest number $ \ge 31 $ whose $ gcdSum $ $ > 1 $ is $ 33 $ . Test case 3: $ \ n = 75 $ : $ \text{ $ gcdSum $ }(75) = gcd(75, 7 + 5) = gcd(75,\ 12) = 3 $ . The $ \text{ $ gcdSum $ } $ of $ 75 $ is already $ > 1 $ . Hence, it is the answer.