Ước chung lớn nhất
Xem PDF
Điểm:
900 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho số nguyên dương N, hãy tìm số nguyên nhỏ nhất X sao cho X >= N và thỏa mãn tính chất sau:
- Y là tổng các chữ số của X trong hệ đếm 10.
- UCLN(X, Y) > 1 (UCLN(X, Y) là ước số chung lớn nhất của X và Y).
Yêu cầu: Tìm số X thỏa mãn yêu cầu.
Dữ liệu vào:
Đọc từ bàn phím số nguyên dương N.
Dữ liệu ra: Xuất ra màn hình một số nguyên dương X thỏa mãn yêu cầu.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra |
|---|---|
| 16 | 18 |
Giải thích: Với N = 16 thì số nguyên nhỏ nhất X thỏa mãn là 18 vì 1 + 8 = 9, UCLN(18, 9) = 9 > 1.
Giới hạn:
- 80% số điểm của bài ứng với các bộ dữ liệu vào có giới hạn N≤104.
- 20% số điểm của bài ứng với các bộ dữ liệu vào có giới hạn 106<N≤1012.
Bình luận
import math
def sd(x):
return sum(int(digit) for digit in str(x))
def gcd(x, y):
return math.gcd(x, y)
def fn(n):
x = n
while True:
y = sd(x)
if gcd(x, y) > 1:
return x
x += 1
N = int(input())
d = fn(N)
print(d)
ez
1 bình luận nữa