自动搬运

查看原文

来自洛谷，原作者为

	晴空一鹤 恰似人间惊鸿客，墨染星辰云水间

搬运于2025-08-24 22:42:40，当前版本为作者最后更新于2022-11-23 15:27:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

看起来像是求 $n$ 在 $\le m$ 的值域是否存在 $2$ 个及以上的因子，然后使用某种优化，其实不是。

不妨回到最原始的暴力，我们考虑让 $n$ 对 $[1,m]$ 范围内的整数取模。

对 $1$ 取模，只有 $1$ 种可能，为 $0$。

对 $2$ 取模，只有 $2$ 种可能，为 $0,1$。

……

直到出现一个数使 $n$ 取模后与前面某个数取模结果相等。

看起来是 $O(m)$ 的？

其实不是，我们可以发现，想让循环继续，$n\bmod2$ 必须是 $1$，因为 $0$ 已经出现过了，$n \bmod 3$ 必须是 $2$，因为 $0,1$ 都已经出现过了...... $n \bmod m$ 必须是 $m-1$，因为 $0,1,2,...,m-2$ 都已经出现过了。

于是我们可以得到一堆同余式，前 $i$ 个同余式的最小解增长迅速，而 $n$ 最多只有 $10^9$，所以这个循环不会循环太多次（经测验最多 $13$ 次）。

所以我们就可以放心大胆的打暴力正解啦！

CODE

#include<bits/stdc++.h>
using namespace std;
int t,n,m;
void inline slove(){
  cin>>n>>m;
  if(m>n+1)
  printf("Yes\n");
  else{
  for(int i=1;i<=m;i++)
  if(n%i!=i-1){
  printf("Yes\n");
  return ;
  }
  printf("No\n");
  }
}
int main(){
   cin>>t;
   while(t--)slove();
}