题解：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}}

时，计算个数即可。

代码

CPP

#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;
}

本文工具使用说明

本文使用洛谷题解格式化工具检查格式。

题解：P14628 [2018 KAIST RUN Fall] Fractions

文章操作

分析

代码

相关推荐

评论

题解：P14628 [2018 KAIST RUN Fall] Fractions