题解：P14628 [2018 KAIST RUN Fall] Fractions

Lolisaki · 2025-11-29 09:43:59 · 题解

题意理解

题中定义“修能分数”，如下：

一个正有理数 \displaystyle \frac{x}{y}，在约分到最简分数 \displaystyle \frac{a}{b} 后，满足 a+b<1000。

现给定 A, B, C, D，满足 A \le x \le B 和 C \le y \le D 时，求有多少个整数对 (x,y) 满足 \displaystyle \frac{x}{y} 是修能分数。

分析

由于题中规定 a+b<1000，数据规模不大，可以枚举 a, b。

设 g=\gcd(x,y)，那么显然易见，x=a \times g，y=b \times g。

因此，对于每一对 (a,b)，寻找满足 A \le a \times g \le B 和 C \le b \times g \le D 的 g 的数量，而这些数量相加的和，就是最终的答案。

AC 代码

::::success[C++ AC 代码]

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

ll A,B,C,D;
ll gmin,gmax;
ll ans;

int main(){
    cin>>A>>B>>C>>D;
    for(ll a=1;a<=998;a++){
        for(ll b=1;a+b<=999;b++){
            if (__gcd(a,b)!=1) continue;
            gmin=max((A+a-1)/a,(C+b-1)/b);
            gmax=min(B/a,D/b);
            if(gmin<=gmax) ans=ans+(gmax-gmin+1);
        }
    }
    cout<<ans<<endl;
    return 0;
}

C++ AC 记录

::::

::::success[Python AC 代码]

from math import gcd

A,B,C,D=map(int,input().split())
ans=0
for a in range(1,999):
    for b in range(1,1000-a):
        if gcd(a,b)!=1:
            continue
        gmin=max((A+a-1)//a,(C+b-1)//b)
        gmax=min(B//a,D//b)
        if gmin<=gmax:
            ans=ans+(gmax-gmin+1)
print(ans)

Python AC 记录

::::