小小小朋友的小小世界

URL: 洛谷

题目描述:

这道题我在参加比赛时居然没想出来……我太弱了

有 $n$ 个人，其中第 $i$ 个人的衣服上有一个数 $i+1$。当一个衣服上的数为 $i$ 的人在某一天被访问了，满足 $gcd(i,j)=1$的人会在第二天被访问。问多久所有人会被访问。

还给了个伯特兰-切比雪夫定理

这个定理可以看百度百科

思路:

基本数论，如果$k+1$为质数，那么如果$k\times 2+1>n$，就说明一天就可以了。否则答案即为2，是因为那个定理，必有一个素数可以被访问，并且它能直接把所有的都访问

注意$longlong$

代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,k;
bool is_prime(ll x){
    if(x==1) return false;
    if(x==2) return true;
    for(ll i=2;i<=sqrt(x);i++){
        if(x%i==0) return false;
    }
    return true;
}
int main(){
    scanf("%lld%lld",&n,&k);
    if(is_prime(k+1)&&(2*(k+1)>n+1)){
        printf("1\n");
    }
    else printf("2\n");
    return 0;
}