CF Gym 102059H Fractions(思维题)

链接：https://codeforces.com/gym/102059/problem/H

题意：求多少对(x，y)，满足A<=x<=B ; C<=y<=D，而且（x+y）/gcd(x,y)<1000

题解：我们枚举化简后的x'=x/gcd; y'=y/gcd；然后看有多少gcd可以满足给定区间的条件，注意上界取min（），下界取max（），因为是相减，最后A-1， B-1；

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

int main()
{
    long long A, B, C, D;
    cin>>A>>B>>C>>D;
    long long ans=0;
    for(int x=1; x<1000; x++)
        for(int y=1; y<1000-x; y++)
        {
            if(__gcd(x, y)!=1) continue;
            long long tmp=min(B/x, D/y)-max((A-1)/x, (C-1)/y); //注意这里A-1，C-1
            if(tmp<=0) continue;
            ans+=tmp;
        }
    cout<<ans;
    return 0;
}