数学、最大公约数与最小公倍数

场切。

由于 $n$ 个人每次要把票投完，所以最后留下的算法数量肯定是 $n$ 的因数。

找到 $n$ 的最小质因数 $k$，如果 $k \leq m$ 则可以留下超过 $1$ 种算法，输出 No；否则输出 Yes 因为游戏肯定会结束。注意如果 $n$ 是质数那么它的最小质因数就是自身，事先需要判定 $n$ 是否等于 $1$。

由于 $n,m$ 同阶，暴力分解质因数回答询问的时间复杂度为 $O(\sqrt{n})$。也可以线性筛 $O(n)$ 预处理每个数的最小质因数后 $O(1)$ 回答询问。

#include<bits/stdc++.h>
using namespace std;
int n,m,lim;
void solution(){
    cin>>n>>m,lim=sqrt(n);
    if(n==1) return cout<<"Yes"<<'\n',void();
    for(int i=2;i<=min(lim,m);i++) if(n%i==0) return cout<<"No"<<'\n',void();
    if(n<=m) return cout<<"No"<<'\n',void();
    cout<<"Yes"<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}