网硕互联帮助中心小红的整数操作
时间限制：1 秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
小红拿到了两个正整数
x
,
y
x, y
x,y，她可以进行以下两种操作：
a
a
a。
a
a
a 既是
x
x
x 的因子，也是
y
y
y 的因子，则将两个数同时除以
a
a
a。
小红希望最终两个数都在
[
l
,
r
]
[l, r]
[l,r] 区间内。她想知道最终的
x
x
x 有多少种不同的取值方案？
输入描述
四个正整数
x
,
y
,
l
,
r
x, y, l, r
x,y,l,r，用空格隔开。
1
≤
x
,
y
,
l
,
r
≤
10
9
1 \\le x, y, l, r \\le 10^9
1≤x,y,l,r≤109
输出描述
一个整数，代表最终
x
x
x 的取值方案。
示例 1
输入：
2 3 2 6
输出：
2
说明： 第一种方案，不进行任何操作，此时
x
x
x 等于
2
2
2。
第二种方案，将
x
x
x 和
y
y
y 同时乘以
2
2
2，此时
x
x
x 等于
4
4
4。
数据范围
-
1
≤
x
,
y
,
l
,
r
≤
10
9
1 \\le x, y, l, r \\le 10^9
1≤x,y,l,r≤109
解题思路
本题是约分 + 区间计数的简单数学题。给定两个正整数 (x, y)，每次操作可以同时乘以任意整数 (a)，或者同时除以一个既是 (x) 的因子也是 (y) 的因子的 (a)。要求最终两个数都落在区间 ([l, r]) 内，问最终 (x) 有多少种不同的取值。
1. 问题等价转化
- 设 (g = \\gcd(x, y))，则 (x = g \\cdot a,\\ y = g \\cdot b)，其中 (a, b) 互质（(\\gcd(a, b) = 1)）。
- 同时乘以或除以公共因子，本质上只改变公共因子 (g) 的大小，而互质部分的比例 (a : b) 始终保持不变。因此经过任意次操作后，两个数一定形如：
x
′
=
k
⋅
a
,
y
′
=
k
⋅
b
x' = k \\cdot a,\\qquad y' = k \\cdot b
x′=k⋅a,y′=k⋅b 其中 (k) 为某个正整数。 - 题目要求 (x’) 和 (y’) 都落在 ([l, r]) 内，即：
l
≤
k
a
≤
r
,
l
≤
k
b
≤
r
l \\le k a \\le r,\\qquad l \\le k b \\le r
l≤ka≤r,l≤kb≤r - 这等价于对 (k) 的约束：
k
≥
⌈
l
a
⌉
,
k
≥
⌈
l
b
⌉
k \\ge \\left\\lceil \\frac{l}{a} \\right\\rceil,\\quad k \\ge \\left\\lceil \\frac{l}{b} \\right\\rceil
k≥⌈al⌉,k≥⌈bl⌉k
≤
⌊
r
a
⌋
,
k
≤
⌊
r
b
⌋
k \\le \\left\\lfloor \\frac{r}{a} \\right\\rfloor,\\quad k \\le \\left\\lfloor \\frac{r}{b} \\right\\rfloor
k≤⌊ar⌋,k≤⌊br⌋ - 由于 (a, b) 互质且 (x’) 的不同取值由 (k) 的不同取值唯一决定（(x’ = k a)），问题转化为求满足上述条件的正整数 (k) 的个数。
2. 简化计算
- 令 (m_1 = \\min(a, b))，(m_2 = \\max(a, b))。因为要求两个数都不小于 (l)，所以 (k) 的下界由较大的分母决定？实际上：
- (k \\ge \\lceil l/a \\rceil) 且 (k \\ge \\lceil l/b \\rceil)，因此 (k \\ge \\lceil l / m_1 \\rceil)。
- (k \\le \\lfloor r/a \\rfloor) 且 (k \\le \\lfloor r/b \\rfloor)，因此 (k \\le \\lfloor r / m_2 \\rfloor)。
- 记
L
=
⌈
l
m
1
⌉
,
R
=
⌊
r
m
2
⌋
L = \\left\\lceil \\frac{l}{m_1} \\right\\rceil,\\qquad R = \\left\\lfloor \\frac{r}{m_2} \\right\\rfloor
L=⌈m1l⌉,R=⌊m2r⌋ - 整数 (k) 的个数为 (\\max(0, R – L + 1))。
- 代码中采用等价变形：
le
=
⌊
l
−
1
m
1
⌋
=
L
−
1
,
ri
=
⌊
r
m
2
⌋
=
R
\\text{le} = \\left\\lfloor \\frac{l-1}{m_1} \\right\\rfloor = L – 1,\\qquad \\text{ri} = \\left\\lfloor \\frac{r}{m_2} \\right\\rfloor = R
le=⌊m1l−1⌋=L−1,ri=⌊m2r⌋=R 因此答案 (= \\max(0, \\text{ri} – \\text{le}))，与 (R – L + 1) 完全一致。
3. 算法步骤
4. 复杂度分析
- 时间复杂度：求最大公约数使用欧几里得算法，复杂度 (O(\\log \\min(x, y)))；其余为常数次算术运算。总时间复杂度 (O(\\log \\min(x, y)))。
- 空间复杂度：仅使用常数个变量，(O(1))。
总结
通过约去最大公约数，将两个数的比例固定为互质的 (a : b)。最终两个数均为比例乘以同一个正整数 (k)。根据区间 ([l, r]) 对 (k) 的上下界约束，直接计算满足条件的 (k) 的个数，即为最终 (x) 的不同取值数量。方法简洁且高效，完美解决了大范围数据下的计数问题。
代码内容
#include <bits/stdc++.h>
using namespace std;
#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1e3+10;
const ll INF=1e18;
const ll M=1e6+10;
const ll mod=1e9+7;
void solve()
{
ll a,b,c,d;
cin>>a>>b>>c>>d;
ll g=__gcd(a,b);
a=a/g;
b=b/g;
ll m1=min(a,b);
ll m2=max(a,b);
ll le=(c–1)/m1;
ll ri=d/m2;
ll res=max(0LL,ri–le);
cout<<res<<'\\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
solve();
return 0;
}
评论前必须登录！
注册