P5535 【XR-3】小道消息

URL: 洛谷

题目描述:

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

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

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

这个定理可以看百度百科

思路:

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

注意$longlong$

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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;
}