题解：P14628 [2018 KAIST RUN Fall] Fractions

· · 题解

分析

显然，直接双重循环会超时。

我们可以枚举合法数对，不满足最简分数的 (a,b) 数对直接跳过。

合适的通过成倍数放大得到 (x,y) 数对。

设放大倍数为 z。

通过把据题意得到的式子 A \le a \times z \le B 以及 C \le b \times z \le D 可以得到 z_{\text{min}} = \max\left(\left\lceil \frac{A}{a} \right\rceil, \left\lceil \frac{C}{b} \right\rceil\right) 和 z_{\text{max}} = \min\left(\left\lfloor \frac{B}{a} \right\rfloor, \left\lfloor \frac{D}{b} \right\rfloor\right) 这两个式子。

当 z_{\text{min}} \le z_{\text{max}} 时，计算个数即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
main() 
{
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int ans=0;
    for(int i=1;i<=998;i++)
    {
        int m1=999-i;
        if(m1<1) continue;
        for(int j=1;j<=m1;j++)
        {
            if(__gcd(i,j)!=1) continue;
            int m2=(a+i-1)/i;
            int m3=(c+j-1)/j;
            int m4=max(m2, m3);
            int m5=b/i;
            int m6=d/j;
            int m7=min(m5,m6);
            if(m4<=m7) ans+=m7-m4+1;
        }
    }
    cout<<ans<<endl;
    return 0;
}

:::info[本文工具使用说明] 本文使用洛谷题解格式化工具检查格式。 :::