题解：P14628 [2018 KAIST RUN Fall] Fractions

zxcar999 · 2025-11-29 10:10:59 · 题解

题解：P14628 [2018 KAIST RUN Fall] Fractions

这题很容易让人想到暴力，So。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,c,d;
int ans;
int gcd(int a,int b) {
    while(b!=0) {
        int tmp=b;
        b=a%b;
        a=tmp;
    }
    return a;
}
signed main(){
    cin>>a>>b>>c>>d;
    for(int i=a;i<=b;i++){
        for(int j=c;j<=d;j++){
            //cout<<i<<" "<<j<<" ";
            int yue=gcd(i,j);
            //cout<<yue<<endl;
            if(i/yue+j/yue<1000){
                ans++;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

当然 10^{12} 的量也不是闹着玩的，在#3就TLE了😭😭😭。
那么正向的唯一方法既然行不通，我们是不是可以枚举 \frac{x}{y} 呢？
既然 x+y < 1000 ，那么分别枚举x，y时间复杂度不可能超过 10^6 而且还有至少 2000 个x，y是 x+y \ge 1000 必然不会TLE。
然后 \gcd(x,y) 在算出a，b，c，d对应x，y的倍数区间范围，取两个区间的交集个数即可。
AC代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,c,d;
int ans;
int gcd(int a,int b) {
    while(b!=0) {
        int tmp=b;
        b=a%b;
        a=tmp;
    }
    return a;
}
signed main(){
    cin>>a>>b>>c>>d;
    for(int i=1;i<1000;i++){//枚举x，y
        for(int j=1;j<1000;j++){
            if(i+j>=1000||gcd(i,j)!=1) continue;//不互质或x+y大于等于1000（舍去）
            int ax=(a+i-1)/i;
            int bx=b/i;
            int cx=(c+j-1)/j;
            int dx=d/j;//求x,y的倍数区间
            int maxa=min(bx,dx);
            int mina=max(ax,cx);//取交集
            if(maxa>=mina) ans+=(maxa-mina+1);//防止无交集
        }
    }
    cout<<ans<<endl;
    return 0;
}