题解：P14628 [2018 KAIST RUN Fall] Fractions

· · 题解

P14628 [2018 KAIST RUN Fall] Fractions 题解

思路

设 g = \gcd(x, y)，则 x = g \times i，y = g \times j，其中 i 和 j 互质。

我们可以枚举 i 和 j，满足以下条件：

对于每一对既约分数 (i, j)，原分数为 \dfrac{x}{y} = \dfrac{g \times i} {g \times j}。

我们要找出 g 的个数，使得

\begin{aligned} A \leq g \times i \leq B \\ C \leq g \times j \leq D \end{aligned}

如果 \max \leq \min，则 g 的个数为 \min - \max + 1，否则为 0。

将所有既约分数对应的 g 个数累加，就是最终答案。

代码

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

#define int long long 
int a, b, c, d;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> a >> b >> c >> d;

    int ans = 0;
    for(int i = 1; i <= 999; i++){
        for(int j = 1; i + j <= 999; j++){
            if(__gcd(i, j) != 1) continue;

            int g_min = max((a + i - 1) / i, (c + j - 1) / j);
            int g_max = min(b / i, d / j);

            if(g_min <= g_max){
                ans += g_max - g_min + 1;
            }
        }
    }

    cout << ans;

    return 0;
}

这是我的第一篇题解，求大家手滑点个赞和关注再走吧 qwq