关注我,分享高质量每日一题题解~
b站同名账号分享力扣杯历届真题视频题解,也欢迎大家提出宝贵意见!
思路:数学
- 根据题目要求,要求对于区间内全部元素 x∈[l,r] 均有 x%a≥a/2,那么必有 l≥ka+a/2其中 k≥0,且 r<(k+1)a否则该区间内一定有某一元素模 a 余 0,不满足题意。
- 联立两个不等式,有 r−l<(k+1)a−(ka+a/2)=a/2我们将该不等式右边放大,有 r−l<a/2≤ka+a/2≤l 故有 r<2l,此时存在满足题意的 a ,否则不存在。直接 O(1) 判断即可。
代码(C++)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int T;
cin >> T;
while(T--) {
ll l, r;
cin >> l >> r;
if(r < 2 * l) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
这个似乎只是说明了必要条件,你只能说明当 r>=2l 的时候是不成立的,事实上在r<2l的时候直接取a=r+1即可,因为此时对于任意一个[l,r]中的x,都有x mod a = x,而x>=l>=r/2+1>a/2
补个证明:
设r=pl,那么有(ka+a2)p≤pl<(k+1)∗a化简得 p<k+1k+12≤2
还感觉放大那里不能随便放大,你放宽条件得说明一下可以取到你放宽条件之后得结果
放宽条件是 k >= 0,但是因为前一个不等式是小于,所以中间这个放宽过程取到与否影响不大。
感觉严谨性有点问题, 因为只证明了必要性, 却没有很好的说明 r < 2l 可以推导出 for x in [l, r], 存在 a 使得x % a >= a / 2
这次nice了,证明一气呵成。如果把推导公式变成行公式,我原称为最好得题解。