[C++知识库]十三届蓝桥杯决赛题目--取模 (C/C++ 大学C组)

一、原题

引用：蓝桥杯2022年第十三届决赛真题-取模（C/C++/Java组） - C语言网

考试时乍一眼是中国剩余定理，1e9开方也是13...14...啥的，数据范围不是很大，当时一看到T的数据范围就挺担心，因为笔者是python组，遇到卡常数就很烦，而且也无法用c++完成题目，

后背顿时凉一半了，不过我想这毕竟是OI赛制，应该还能得点分吧。。。

二、思路-中国剩余定理

命题 :? 给定整数 n,m （n>=m>=1），问当赋值给变量k = 1、2、3、...、m 的变化过程中，n mod k 是否能刚好取遍[0，m-1)；

我们进一步提炼命题 : n mod k?≡ (k - 1) 是否能在 k ∈ [1,m) 中始终成立?。

如果命题为真，那么n mod 1 = 0，那么n mod 2 必为?1... ?

可得出如下图的同余方程组：

不难可以推出：当n满足以上同余方程组，那么将不存在一对不相同的 x,y 满足 n mod x = n mod y 且 1 <= x < y <= m；

我们可以举个例子，当命题为真，n满足以上同余方程组，设x,y分别为1,2 (m >=2)，那么我们可以发现 n mod 1 与 n mod 2 是不相等的。

综上，我们也不难得出：n mod m! 的唯一解为 m! - 1?

然，由题意得：数据范围最大是1e9，开方后得到m 取?13。也就是说，我们只需要枚举不超过十三个数，就可以判断n,m能否满足以上同余方程组，进而判断n,m是否满足原命题。

三、代码实现

PS：用c++ + 快读不香吗！！ 笔者还未发现Python的快读快写方法，有知道的小伙伴请多多指教！阿里噶多！！? ? ?

#include<bits/stdc++.h>

int read() {
    register int x = 0,f = 1;register char ch;
    ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
    while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
    return x * f;
}

int main(){
	int x;
	long long n,m;
	x = read();
	for (long long j = 1;j <= x;j ++){
		n = read();m = read();
		if (m > 13) m = 13;
		bool flag = false;
		for (int i = 2;i <= m;++i){
			if (n % i != i - 1) 
				flag = true;
			if (flag) break;
		}
		printf((flag ? "Yes\n" : "No\n"));
	}
	return 0;
} 

有问题或者有更多想法的小伙伴，请在评论区提出指导意见，谢谢！