C. Cave Painting(最小公倍数的应用)

\(\color{Red}{网上的题解都是投机取巧啊，虽然也没错}\)

\(Ⅰ.先说一下投机取巧的方法\)
\(自己写几个例子会发现k很小的时候满足条件的n就变得很大\)
\(所以我们直接暴力从1判断到n,如果不满足就跳出循环\)

\(\color{Purple}{Ⅱ.正解(个人认为)}\)
\(因为n\pmod1=0\)
\(所以要满足条件一定是\)
\(n\pmod2=1\)
\(n\pmod3=2\)
\(.....................\)
\(n\pmod{k}=k-1\)

\(所以我们知道,n+1可以整除(1-k)的所有数\)

\(那我们从1到k求一个最小公倍数\)

\(如果求出来的最小公倍数是(n+1)的因子说明可行,否则不可行\)

\(如果求得过程中最小公因数比(n+1)还大说明不可行\)

\(有不懂欢迎留言................\)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){
    if(!b)  return a;
    else    return gcd(b,a%b);
} 
ll n,k;
int main()
{
    cin>>n>>k;
    if(k==1)    cout<<"Yes";
    else
    {
        ll jie=1;
        for(ll i=2;i<=k;i++)
        {
            jie=jie*i/gcd(jie,i);//慢慢求最小公倍数 
            if(jie>n+1)  break;//大于就提前退出 
        }
        if((1+n)%jie==0)    cout<<"Yes";
        else    cout<<"No"; 
    }
}