题解：P14628 [2018 KAIST RUN Fall] Fractions

· · 题解

枚举修能分数的分子和分母，算一下分子放大到 a\sim b 之间可行的放大倍数区间和把分母放大到 c\sim d 之间的可行的放大倍数区间。求一下区间交集长度即可。

注意左端点那里，放大要向上取整。

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

#define ll long long
#define up(l,r,i) for(int i=(l);i<=(r);++i)

ll a,b,c,d,ans;

ll ceildiv(ll x,ll y){
    return (x+y-1)/y;
}

int main(){
    cin>>a>>b>>c>>d;
    up(1,999,x){
        up(1,999,y){
            if(x+y>999)continue;
            if(__gcd(x,y)>1)continue;
            if(x>b||y>d)continue;
            ll l=ceildiv(a,x),r=b/x,_l=ceildiv(c,y),_r=d/y;
            if(r<_l||_r<l)continue;
            l=max(l,1ll),_l=max(_l,1ll);
            ll L=max(l,_l),R=min(r,_r);
            if(L<=R)ans+=R-L+1;
        }
    }
    cout<<ans;
}