[NOIP 2008 提高组] 笨小猴

知识点

字符串、频次统计、素数判定

解题思路

统计26个字母的出现次数，仅在出现过的字母中取最小值，计算最大与最小频次之差d，再试除判断d是否为质数。

正确性说明

频次数组精确记录每个字母的出现次数，取非零最小值与整体最大值即符合定义。试除到sqrt(d)即可找到任何合数的非平凡因子，因此质数判定正确。

易错点

没有出现的字母不能参与最小频次；0和1不是质数；不幸运时第二行必须输出0。

复杂度

设字符串长L，时间O(L+26+sqrt(L))，空间O(26)=O(1)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;cin>>s;int cnt[26]={};for(char c:s)++cnt[c-'a'];
    int lo=INT_MAX,hi=0;for(int x:cnt)if(x){lo=min(lo,x);hi=max(hi,x);}
    int d=hi-lo;bool prime=d>=2;for(int i=2;i*i<=d;++i)if(d%i==0)prime=false;
    if(prime)cout<<"Lucky Word\n"<<d<<'\n';else cout<<"No Answer\n0\n";
}