Hướng dẫn cho Summer Contest #02 - Câu đố giờ nghỉ

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: ledinhbaonam, uia

Ý tưởng

Điều kiện khó chịu nhất của bài là:

\[ \frac{b}{a}<\frac{f}{e}<\frac{d}{c} \]

Nếu dùng số thực sẽ rất dễ gặp sai số, vì vậy ta chuyển toàn bộ về phép so sánh số nguyên bằng cách nhân chéo:

\[ b\cdot e<a\cdot f \]

và

\[ c\cdot f<d\cdot e. \]

Như vậy việc kiểm tra một cặp \((e,f)\) chỉ còn là vài phép nhân.

Tiếp theo, đề bài yêu cầu:

\[ |e-f|=n. \]

Với một số nguyên tố \(e\) cố định thì chỉ có nhiều nhất hai giá trị cần kiểm tra:

\[ f=e-n \]

hoặc

\[ f=e+n. \]

Do đó thay vì duyệt mọi cặp số nguyên tố, ta chỉ cần duyệt từng số nguyên tố \(e\) rồi kiểm tra hai ứng viên trên.

Vì:

\[ s\le10^7 \]

nên hoàn toàn có thể sàng Eratosthenes để biết số nào là số nguyên tố.

Sau khi sàng xong, với mỗi số nguyên tố \(e\):

Xét \(f=e-n\).
Xét \(f=e+n\).

Nếu:

\(f\) là số nguyên tố.
\(e+f\le s\).
Thỏa mãn điều kiện phân số.

thì tăng đáp án lên \(1\).

Code AC (C++)

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("caudogionghi.inp","r",stdin);
    freopen("caudogionghi.out","w", stdout);
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    int n, s;
    cin >> n >> s;
    vector<bool> isPrime(s + 1, true);
    if (s >= 0) isPrime[0] = false;
    if (s >= 1) isPrime[1] = false;
    for (long long i = 2; i * i <= s; i++) {
        if (isPrime[i]) {
            for (long long j = i * i; j <= s; j += i) {
                isPrime[j] = false;
            }
        }
    }
    long long ans = 0;
    for (int e = 2; e <= s; e++) {
        if (!isPrime[e]) {
            continue;
        }
        int f1 = e - n;
        if (f1 >= 2 && f1 <= s && isPrime[f1]) {
            if (e + f1 <= s) {
                long long left1 = b * 1LL * e;
                long long right1 = a * 1LL * f1;
                long long left2 = c * 1LL * f1;
                long long right2 = d * 1LL * e;
                if (left1 < right1 && left2 < right2) {
                    ans++;
                }
            }
        }
        int f2 = e + n;
        if (f2 >= 2 && f2 <= s && isPrime[f2]) {
            if (e + f2 <= s) {
                long long left1 = b * 1LL * e;
                long long right1 = a * 1LL * f2;
                long long left2 = c * 1LL * f2;
                long long right2 = d * 1LL * e;
                if (left1 < right1 && left2 < right2) {
                    ans++;
                }
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

Bình luận (1)

Tải bình luận...