小红整数操作题解

此题可以先求出x,y的最大公约数d,再将两数与其最大公约数相除转化为两个互质的数，同时这里用到了数论的一个结论：一个数a在区间[1,x]的倍数的个数为x/a，这里要注意拿x/d与y/d最小的数相除区间的左端点l时个数应为： l/min(x/d,l/d)+(l%min(x/d,l/d)!=0) 因为当不能整除时我们只有取后一个数与最小值相乘才能在区间[l,r]内，答案即为最大值在[1,r]区间的倍数的个数-最小值在区间[1,l]的倍数+1。

#include<set>
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
using ll=long long ;
using pii=pair<int,int> ;
#define endl "\n"

constexpr int N=1e5+10;
constexpr int mod=1e9+7;


void solve()
{
    int x,y,l,r;
    cin>>x>>y>>l>>r;
    
    int d=__gcd(x,y);
    int a=min(x/d,y/d),b=max(x/d,y/d);
    int v1=l/a+(l%a!=0),v2=r/b;
    
    if(v2<v1)cout<<0<<endl;
    else cout<<v2-v1+1<<endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    int t;
    t=1;
    
    while(t--)
    solve();
    return 0;
}