https://codeforces.com/contest/1498/problem/A
시간 1초, 메모리 256MB
input :
- t (1 ≤ t ≤ 104)
- 숫자 n
output :
- Output t lines, where the i-th line is a single integer containing the answer to the i-th test case.
각 테스트케이스의 정답을 출력하시오.
조건 :
-
The gcdSum of a positive integer is the gcd of that integer with its sum of digits.
정수의 gcdSum이란 그 수와 각 숫자들의 합의 최대 공약수를 의미한다. -
gcdSum(762) = gcd(762, 7 + 6 + 2) = gcd(762, 15) = 3.
-
Given an integer n, find the smallest integer x ≥ n such that gcdSum(x) > 1.
정수 n이 주어졌을 때 x ≥ n의 정수들 중에서 gcdSum(x) > 1을 만족하는 가장 작은 x를 찾으시오.
코드를 작성한 것은 그냥 완전탐색을 통해 가장 먼저 위의 조건을 만족하는 숫자를 출력하도록 하였다.
문제의 풀이에서는 숫자가 3의 배수인 경우의 특징을 사용해서 문제를 해결한다. 3의 배수인 경우 위의 각 숫자들을 더한다면 이 수는 3의 배수를 이룬다. 그래서 최대 공약수는 3보다 크거나 같게 된다. 그래서 입력 받은 숫자의 위로 3의 배수를 찾는 것이다.
물론 위의 규칙을 찾지는 못했지만 최대공약수가 1보다 커지는 것이기에 두 수가 서로소만 아니면 답을 준다는 생각에 그냥 완전 탐색을 하였다.
import sys
import math
def check(num):
while True:
temp, temp_ans = num, 0
while temp > 0:
temp_ans += temp % 10
temp //= 10
ans = math.gcd(num, temp_ans)
if ans > 1:
return num
num += 1
for _ in range(int(sys.stdin.readline())):
n = int(sys.stdin.readline())
print(check(n))
