[蓝桥杯 2022 国 C] 取模题解

晴空一鹤 · 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();
}