Ước chung lớn nhất

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
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


  • 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
      Khanglp    5:54 p.m. 26 Tháng 8, 2024

      bro làm sai chứ t vẫn AC bình thường mà


      • 0
        bacnewbie    11:24 a.m. 7 Tháng 9, 2024

        include <bits/stdc++.h>

        using namespace std;
        long long n; int res;
        int tcs(long long a) {
        long long x; int t;
        x=a;
        while (x>0) {
        t+= (x%10);
        x/=10;
        }
        return t;
        }
        int main(){
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cin>>n; res=tcs(n);
        while (gcd(n,res)==1) { n++; res=tcs(n); }
        cout<<n;
        return 0;
        }
        ban xem minh sai o dau voi chu minh nhap input no ra output dung ma vao cham thi sai ;-;

    1 bình luận nữa