【题目来源】
洛谷：P1125 [NOIP 2008 提高组] 笨小猴 - 洛谷
【题目描述】
笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！
这种方法的具体描述如下：假设 \(maxn\) 是单词中出现次数最多的字母的出现次数，\(minn\) 是单词中出现次数最少的字母的出现次数，如果 \(maxn−minn\) 是一个质数，那么笨小猴就认为这是个 Lucky Word，这样的单词很可能就是正确的答案。
【输入】
一个单词，其中只可能出现小写字母，并且长度小于 \(100\)。
【输出】
共两行，第一行是一个字符串，假设输入的的单词是 Lucky Word，那么输出 Lucky Word，否则输出 No Answer；
第二行是一个整数，如果输入单词是 Lucky Word，输出 \(maxn−minn\) 的值，否则输出 \(0\)。
【输入样例】
error
【输出样例】
Lucky Word
2
【算法标签】
《洛谷 P1125 笨小猴》 #素数判断,质数,筛法# #NOIP提高组# #2008#
【代码详解】
#include <bits/stdc++.h> // 包含标准库头文件（万能头文件）
using namespace std; // 使用标准命名空间/*** 判断一个数是否为质数* @param n 待判断的数字* @return 如果是质数返回true，否则返回false*/
bool fun(int n)
{if (n < 2) return false; // 小于2的数不是质数// 检查从2到n-1是否有因数for (int i = 2; i < n; i++) {if (n % i == 0) return false; // 有因数则不是质数}return true; // 否则是质数
}int main()
{string s; // 定义字符串：存储输入的单词int maxn = 0; // 定义变量：字母出现次数的最大值int minn = 100; // 定义变量：字母出现次数的最小值（初始设为较大值）int t; // 定义变量：最大值与最小值的差int mark = 0; // 定义变量：未使用的标记变量（代码中未使用）int counts[150] = {0};// 定义数组：统计每个ASCII字符出现的次数cin >> s; // 输入单词// 统计每个字母出现的次数for (int i = 0; i < s.length(); i++) {counts[s[i]]++; // 对应字符的计数器加1}// 遍历a-z的ASCII码范围，找出最大和最小出现次数for (int i = 'a'; i <= 'z'; i++) {if (counts[i] > maxn) maxn = counts[i]; // 更新最大值// 更新最小值（忽略出现次数为0的字母）if (counts[i] < minn && counts[i] != 0) minn = counts[i];}t = maxn - minn; // 计算最大值与最小值的差// 判断差值是否为质数并输出结果if (fun(t)) {cout << "Lucky Word" << endl << t; // 是质数} else {cout << "No Answer" << endl << 0; // 不是质数}return 0; // 程序正常结束
}
【运行结果】
olympic
No Answer
0