Ước chung lớn nhất

Xem PDF



Dạng bài
Ngôn ngữ cho phép
C++, Python
Đ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


  • -1
    minhquannguyenphuc2013    5:32 p.m. 28 Tháng 8, 2024

    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 phản hồi

    • 0
      bacnewbie    4:45 p.m. 26 Tháng 8, 2024

      may cham loi a dm t chay test dung vao cham thi sai

      1 phản hồi