P5535 【XR-3】小道消息

2019-08-30 21:37:52


题目描述:

有 $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;
}