UVa

Luogu

Vjudge

分析

显然,最差的情况是每次询问的回答都是 $1$ 。因为如果不是 $1$ 的话范围一定减小。

显然,每次都猜一些质数的积是最好的。因为如果不猜质数的话答案不会变优。

以上结论可以感性理解,证明不会

于是问题就变为给 $n$ 以内的质数分组,使得每组的积都不超过 $n$ ,并且组数最少。

考虑贪心:对于后面的质数,找前面的一些质数使得积不超过 $n$ ,然后分成一组。

正确性感性理解即可,证明也不会

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10000+10;

int p[N],v[N],cnt;

inline void sieve(int n) {
    cnt=0;
    for (re int i=2;i<=n;++i) {
        if (!v[i]) p[++cnt]=i;
        for (re int j=1;j<=cnt&&i*p[j]<=n;++j) {
            v[i*p[j]]=1;
            if (i%p[j]==0) break;
        }
    }
}

int main() {
    int n;
    while (scanf("%d",&n)==1) {
        sieve(n); int ans=0;
        for (re int h=1,t=cnt;t-h+1;) {
            int now=p[t];
            while (t-h+1>=2&&now*p[h]<=n) now*=p[h],++h;
            --t,++ans;
        }
        printf("%d\n",ans);
    }
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 49 PM