DHBB 2026 - DX01 - 10 - Số không giống

Xem dạng PDF

Gửi bài giải

Điểm: 11,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout
Test chính thức

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Gọi hai số tự nhiên ~x~ và ~y~ là không giống nhau nếu chúng khác nhau và không có hai số ~a~, ~b~ khác nhau (khác ~1~) sao cho ~x~ và ~y~ đều chia hết cho cả ~a~ và ~b~. Ví dụ, ~6~ và ~9~ không giống nhau vì chúng chỉ chia hết cho ~3~ (khác ~1~).

Cho một số tự nhiên ~x~ và các số tự nhiên ~l~, ~r~. Cần phải tìm tất cả các số ~y~ sao cho ~l \le y \le r~ sao cho ~x~ và ~y~ không giống nhau.

Input

Dòng đầu chứa số ~x~ ~(1 \le x \le 10^9)~.

Dòng thứ hai và dòng thứ ba lần lượt chứa các số tự nhiên ~l~, ~r~ ~(1 \le l \le r \le 10^9, r - l \le 1000)~.

Output

Dòng đầu tiên in ra số ~k~ là số các số không giống nhau với ~x~ trên đoạn từ ~l~ đến ~r~.

Dòng thứ hai in ra tất cả các số này theo thứ tự tăng dần.

Sample Input 1

18
1
15

Sample Output 1

12
1 2 3 4 5 7 8 10 11 13 14 15

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 0
    missmphuog  đã bình luận lúc 2, Tháng 11, 2026, 16:17
    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long
    
    bool nt(ll n) {
        if (n < 2) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;
    
        for (ll i = 3; i * i <= n; i += 2) {
            if (n % i == 0)
                return false;
        }
    
        return true;
    }
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    
        ll x, l, r;
        cin >> x >> l >> r;
    
        vector<ll> ans;
    
        for (ll y = l; y <= r; y++) {
            if (y == x) continue;
    
            ll g = __gcd(x, y);
    
            if (g == 1 || nt(g))
                ans.push_back(y);
        }
    
        cout << ans.size() << '\n';
    
        for (ll y : ans)
            cout << y << ' ';
    
        cout << '\n';
        return 0;
    }