luogu5535 小道消息

分析

关于伯特兰·切比雪夫定理，我们只需要用百科里说的“较弱”的说法。

对于整数 \(n \ge 1\)，至少存在一个质数 \(p\)，满足 \(p \in (n,2n)\)。

有什么用？

首先 \(k \in [1,n]\)，由于每个人衣服上的数是下标 +1，那么第 \(k\) 个人衣服上的数就满足 \(k+1 \ge 1\)。从而 \((k+1,2k+2)\)，也就是 \([k+2,2k+1]\) 之中必定有一个质数。

如果 \(k+1\) 是个质数，那么显然除了它的倍数之外的数，与它的最大公约数都为 1。那么只要保证它的最小倍数 \(2k +2 > n+1\) 就能 1 天就传达完成。

那如果 \(k+1\) 不是质数呢？根据质数的分布传给上面那样的质数就行了，2 天。

CODE

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

P1414 又是毕业季II

分析

定义 \(p_i\) 表示质因数 \(i\) 在每个能力值中出现的次数。

明确对于 \(k=i,j\) 其中 \(i > j\)，所输出的最大默契程度必然是单调不增的。因为多选一个人不会让最大公约数变大。

当 \(k=1\) 时，答案是最大的能力值，设其为 \(mx\)。那么就令 \(ans=mx\)，如果 \(p_{ans} < i\)，那么让 \(ans-1\)，这样一定是最大的。

CODE

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e4+5, M=1e6+5;
int n, a[N], p[M];
int main() {
    int mx=0;
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]), mx=max(mx,a[i]);
    for(int i=1;i<=n;++i) {
        for(int j=1;j*j<=a[i];++j) if(a[i]%j==0) {
            ++p[j];
            if(j*j!=a[i]) ++p[a[i]/j];
        }
    }
    int ans=mx;
    for(int i=1;i<=n;++i) {
        while(p[ans]<i) --ans;
        printf("%d\n",ans);
    }
}