题解 P1125 【笨小猴】
顾z
2018-08-19 21:08:21
**题目描述**
笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！
这种方法的具体描述如下：假设maxn是单词中出现次数最多的字母的出现次数，minn是单词中出现次数最少的字母的出现次数，如果maxn-minn是一个质数，那么笨小猴就认为这是个Lucky Word，这样的单词很可能就是正确的答案。
**分析:**
其实前人介绍了做法,只是没有见到用筛法做此题的,所以来介绍一下**线性素数筛** ~~(尝试水一篇题解~~
提供板子位置--> [线性筛素数](https://www.luogu.org/problemnew/show/P3383)
我们可以用数组prime[]来存储素数,对于一些素数的倍数,它一定不是素数,所以我们可以利用这一性质去筛除一些素数的倍数。
因此很容易码出**普通筛法**
```cpp
IL void getprime()
{
vis[1]=true;
for(int i=2;i<=n;i++)
{
if(!vis[i])prime[++tot]=i;
for(RI j=1;j<=tot;i*prime[j]<=n;j++)
vis[i*prime[j]]=1;
}
//tot用来记录素数个数
//vis数组为辅助数组判断合数。
//vis[i]为true则i为合数 否则为素数。
}
```
但是这样的话考虑 6既可以被2筛去,也可以被3筛去
同样的数还有很多,即我们重复地筛去了这些合数,
而这里就是我们时间浪费的地方
因此我们可以用一些数的最小质因子将其筛去,所以改变后的代码如下
```cpp
IL void getprime()
{
vis[1]=true;
for(int i=2;i<=n;i++)
{
if(!vis[i])prime[++tot]=i;
for(int j=1;j<=tot;i*prime[j]<=n;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)break;//只是增加了这一句
}
}
//tot用来记录素数个数
//vis数组为辅助数组判断合数。
//vis[i]为true则i为合数 否则为素数。
}
```
什么?两层for不是线性的？
~~具体我也不会证明~~
百度见[贾志鹏线性筛](https://wenku.baidu.com/view/542961fdba0d4a7302763ad5.html)
此题代码↓
```cpp
#include<bits/stdc++.h>
#define IL inline
#define RI register int
using namespace std;
int prime[105],tot,tong[27],mxx,mnn=2147483647;
bool vis[105];
string s;
IL void p()
{
vis[0]=vis[1]=1;
for(RI i=2;i<=105;i++)
{
if(!vis[i])prime[++tot]=i;
for(RI j=1;j<=tot&&i*prime[j]<=105;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}
int main()
{
p();
cin>>s;
for(RI i=0;i<s.length();i++)
tong[s[i]-'a'+1]++;
for(RI i=1;i<=26;i++)
{
mxx=max(mxx,tong[i]);
if(tong[i]!=0)mnn=min(mnn,tong[i]);
}
if(!vis[mxx-mnn])printf("Lucky Word\n"),print(mxx-mnn);
else printf("No Answer\n"),print(0);
}
```