P8807 [蓝桥杯 2022 国 C] 取模

· · 个人记录

要求不同的x,y：使得： n\% x=n \% y。也就是n-c=a*x=b*y=x*y; 也可以表示为n \%x=c，是否存在不同的x使得n\%x=c成立 我们枚举x和c的所有可能性

n \quad mod \quad x= \begin{cases} 0,\quad x=1\\ 0,1, \quad x=2\\ 0,1,2 \quad x=3\\ 0,1,2...m-1 \quad x=m \end{cases}

假设只有唯一的x使得上面的式子成立。 因为n\%1=0,所以n\%2只能=1 同理：要只有唯一的解，方程只能为：

\begin{cases} n\%2=1\\ n\%3=2\\ n\%4=3\\ ...\\ n\%m=m-1 \end{cases}

那这样的n有多少个呢？根据扩展中国剩余定理n=lcm(2,3,..m)-1有唯一解。 根据题目的数据范围，m只有再较小的情况下才可能成立，经过计算，m<=13

因此，只需要判断n\%i=i-1的情况即可。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n,m;
bool work(){
    scanf("%lld%lld",&n,&m);
//  if(m*(m-1)<n-m+2)return 0;
    if(m>13)m=13;

    for(int k=2;k<=m;k++){
        if(n%k!=k-1)return 1;
    }
    return 0;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        if(work())puts("Yes");
        else puts("No");
    }

}