[蓝桥杯 2022 国 C] 取模（数论/枚举）

第一思路比较容易想到使用暴力嵌套for循环进行解决 即：在【1，m-1】之间枚举每一个x，之后再枚举【x+1，m】之间枚举每一个y，分别计算得到它们与n的取模值，进行比较即可 #include<iostream> #define int long long using namespace std; signed main(){ int t,n,m; cin>>t; while(t--){ cin>>n>>m; int sign=0; for(int i=1;i<=m-1;i++){ int temp=n%i; for(int j=i+1;j<=m;j++){ if(temp==(n%j)){ sign=1; cout<<"Yes"<<endl; break; } } if(sign)break; } if(!sign) cout<<"No"<<endl; } return 0; } 但是很明显看到该题的数据范围，使用O(n^2)是必然超时的

第二思路： 我们可以使用一个容器存储每一个取模后的值，同时对每一个值进行计数，如果某一个取模值在容器中出现的次数出现了>=2次，我们就可以判断Yes 这里的容器可以选择使用set或者是multiset的count函数（当然使用数组也可以实现） #include<iostream> #include<set> #define int long long using namespace std; signed main(){ int t; cin>>t; while(t--){ int n,m; cin>>n>>m; multiset<int>st; int sign=0;//找得到吗 for(int i=1;i<=m;i++){ int temp=n%i; st.insert(temp); if(st.count(temp)>=2){ cout<<"Yes"<<endl; sign=1; break; } } if(!sign)cout<<"No"<<endl; } return 0; }

上述思路还可以进行优化的一点是，我们不难发现当m较大时，必然输出Yes，因此我们选择在m>=30时必然输入Yes signed main(){ //不难发现当m较大时，一定输出Yes，因此只需对m较小时进行暴力计算即可 int t,n,m; cin>>t; while(t--){ multiset<int>st; cin>>n>>m; if(m>=30){ cout<<"Yes"<<endl; }else{ int sign=0;//找得到吗 for(int i=1;i<=m;i++){ int temp=n%i; st.insert(temp); if(st.count(temp)>=2){ cout<<"Yes"<<endl; sign=1; break; } } if(!sign)cout<<"No"<<endl; } } return 0; }

第三思路： 我们考虑从题目的反面进行解答，假设不存在x和y满足题意的话，首先任何数模1都等于0，如果不满足题意的话，那么y模2就不能等于0只能等于1，依次类推某一个数字模3就只能等于2，据此我们就可以写代码了 signed main(){ int t; cin>>t; while(t--){ int n,m,sign=0; cin>>n>>m; if(m>=30){ cout<<"Yes"<<endl; }else{ for(int i=2;i<=m;i++){ if(n%i!=i-1){ sign=1; cout<<"Yes"<<endl; break; } } if(!sign){ cout<<"No"<<endl; } } } return 0; }