第六章 函数¶
基础数学知识¶
- 因子、完全数与亲和数：本章求因子和时不含数本身；完全数的因子和等于自身，亲和数要求两个不同的数互为因子和。对应 1150、1154。
- 质数与成对因子：质数大于 \(1\)，只有 \(1\) 和自身两个正因子；若合数有一对因子，至少一个不超过平方根。对应 1151、1153、1155、1157、1403、1405、1407—1411。
- 分式与代入：先分别求分子、分母，再做除法，分母不能为零。对应 1152、1167。
- 平方根与嵌套根式：\(\sqrt a\) 表示平方为 \(a\) 的非负数；多层根式要从内往外理解。对应 1156、1166。
- 正负交替的求和式与近似：观察每项的幂、分母和符号；截断求和得到近似值，输出位数不等于实际精度。对应 1156。
- 等差数列求和与方程变形：\(1+2+\cdots+y=\frac{y(y+1)}2\)；将门牌关系化为 \(\frac{y(y+1)}2-3x=n\)。对应 1404、1158。
- 向上取整：不足一条的短信也要按一条计费，条数为 \(\lceil x/70\rceil\)。对应 1398。
- 进位制与位权：例如 \((42)_{13}=4\times13+2\)，每个数位必须小于进制；二进制除以 \(2\) 可依次取出低位。对应 1412、1413、1161。
- 余数与循环：循环使用长度为 \(k\) 的密钥可用
i % k；字母偏移按 \(26\) 个字母绕回。对应 1402。 - 数列、递推与递归定义：先给起点，再用较小项定义后续项，例如 \(F_n=F_{n-1}+F_{n-2}\)；调用函数时要逐步靠近起点。对应 1158、1159、1163、1165—1167。
第一节 函数¶
1150：求正整数 2 和 n 之间的完全数¶
提示 1：先只检查一个数
6的真因子是1、2、3，相加正好是6。
先管好一件事，判断传进来的x。
哪些数要输出，等函数写好再说。
提示 2：函数把判断结果交回来
在bool check(int x)里，sum从0开始，把小于x的正因子加进去，最后：
check(6)得到true，check(8)应得到什么？
知识补充
本题 \(n\le5000\)，总和用 int 足够。
第二种方法利用因子成对出现，只查到平方根。
常见错误
不包含数本身，但要包含因子 \(1\)。
成对找因子时，平方根不能重复加。
自测
输入：7 → 预期输出：6
输入：2 → 预期输出：不输出任何字符
输入：5000，预期输出：
自己试试：自己选一个完全数，分别把它和比它小 \(1\) 的数作为上限。
两次输出应相差哪一个数？
方法一：逐个检查因子
方法二：成对寻找因子
#include <bits/stdc++.h>
using namespace std;
bool check(int x) {
int sum = 1;
for (int i = 2; i <= x / i; i++) {
if (x % i != 0) continue;
sum += i;
if (i != x / i) sum += x / i;
}
return sum == x;
}
int main() {
int n;
cin >> n;
for (int i = 2; i <= n; i++)
if (check(i)) cout << i << '\n';
return 0;
}
1151：素数个数¶
提示 1：函数只负责回答是不是质数
is_prime不负责计数，也不负责输出；主函数还需要自己累加答案。
提示 2：找到一个因数就能否定
在bool is_prime(int x)中先排除小于2的数：
全部试完才返回true，为什么不能第一次没除尽就返回true？
知识补充
本题 \(2\le n\le50000\)。
is_prime 找到约数就返回 false，全部试完才返回 true。
常见错误
\(1\) 不是质数，试除要包含平方根。
用 \(4\)、\(9\) 检查循环是否漏掉端点。
自测
输入：10 → 预期输出：4
输入：2 → 预期输出：1
输入：50000 → 预期输出：5133
参考代码
1152：最大数 max (x,y,z)¶
提示 1：先把三次调用圈出来
分子求一次最大值，分母有两次；对照原式，三组参数哪里不同？
提示 2：先完成三个数取最大值
在double maxn(double a, double b, double c)中：
主函数用它分别算x、y、z，最后代入x / (y * z)，别把乘积漏成只除一个数。
知识补充
题目中的关系是
题目要求分别用函数和过程实现，第二种用 void 函数表示过程。
double &ans 让函数能够修改调用处传入的变量，不是再复制一份。
分母为零时分式没有定义，题面未给出此时的输出规则，不另编输出。
常见错误
不要把 maxn(a + b, b, c) 看成 maxn(a, b, c)。
用 double 计算，保留三位小数。
自测
输入：1 2 3 → 预期输出：0.200
输入：2 4 6 → 预期输出：0.100
方法一：用返回值带回最大值
方法二：用引用参数带回最大值
1153：绝对素数¶
提示 1：把13倒过来再检查
13和31都是质数，而19倒过来是91，能通过吗？
常见错误
“绝对素数”在本题中只要求两位交换后仍是质数。
不要补成其他题里的“任意排列都为质数”。
参考代码
#include <bits/stdc++.h>
using namespace std;
bool is_prime(int x) {
if (x < 2) return false;
for (int i = 2; i <= x / i; i++)
if (x % i == 0) return false;
return true;
}
int main() {
for (int i = 10; i <= 99; i++) {
int x = i % 10 * 10 + i / 10;
if (is_prime(i) && is_prime(x)) cout << i << '\n';
}
return 0;
}
1154：亲和数¶
提示 1：一个因子和还不够
设a的真因子和为b，还要检查b的真因子和等于谁？
完全数的因子和等于自身，但这里要求两数不同。
提示 2：函数返回因子和
写factor_sum(x)，只加小于x的正因子；成对求因子时，平方根只加一次。
这句放在i为因数、且已加i之后。
提示 3：按小的成员从前往后找
枚举a，先算b = factor_sum(a)：
为什么a等于b时不能进入？
知识补充
用 \(16\) 检查求和函数：因子是 \(1,2,4,8\)，和为 \(15\)。
如果把 \(4\) 加了两次，成对求因子的写法就有问题。
常见错误
不能把完全数当成亲和数，题目要求两个数不同。
因子和不含自身，平方根因子只加一次。
自测
无需输入，预期输出：220 284
参考代码
#include <bits/stdc++.h>
using namespace std;
int factor_sum(int x) {
if (x <= 1) return 0;
int sum = 1;
for (int i = 2; i <= x / i; i++) {
if (x % i != 0) continue;
sum += i;
if (i != x / i) sum += x / i;
}
return sum;
}
int main() {
for (int a = 2; ; a++) {
int b = factor_sum(a);
if (a < b && factor_sum(b) == a) {
cout << a << ' ' << b;
break;
}
}
return 0;
}
1155：回文三位数¶
提示 1：两道检查分开过
121左右相同，但11乘11等于121，为什么不能输出？
提示 2：三位回文只比较首尾
在bool is_palindrome(int x)中：
主函数枚举100到999，还要用&&接上is_prime；这里的回文函数只针对三位数。
常见错误
\(121\) 是回文数，却不是质数。
三位数要从 \(100\) 检查到 \(999\)。
参考代码
#include <bits/stdc++.h>
using namespace std;
bool is_palindrome(int x) {
return x / 100 == x % 10;
}
bool is_prime(int x) {
if (x < 2) return false;
for (int i = 2; i <= x / i; i++)
if (x % i == 0) return false;
return true;
}
int main() {
for (int i = 100; i <= 999; i++)
if (is_palindrome(i) && is_prime(i)) cout << i << '\n';
return 0;
}
1156：求 π 的值¶
提示 1：先把项的变化列出来
题面给了求和式，不要求先学反三角函数。
分子是x、三次方、五次方，分母是1、3、5，符号怎样轮换？
提示 2：当前项加完后再更新
在arctanx中，分子numerator初值x、分母denominator初值1、sign初值1，sum从0开始：
自己用正负两项跟踪，看符号是否轮换。
提示 3：停止看项，不是看总和
用fabs(numerator / denominator)与eps比较，不足阈值时停止加入。
函数返回sum，主函数再乘6；十位小数是输出格式，不代表截断误差小于十位小数。
知识补充
按题目给出的求和式计算，不需要先学会反三角函数。
这是无限求和式，不能称作有限项多项式。
参考代码沿用原有截断写法，首个绝对值不足 \(10^{-6}\) 的项不再加入。
常见错误
负数项不能直接与正的阈值比较。
输出十位小数是格式要求，不代表这个截断结果有十位精度。
自测
无需输入，预期输出：3.1415905109
参考代码
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-6;
double arctanx(double x) {
double sum = 0, numerator = x;
int denominator = 1, sign = 1;
while (fabs(numerator / denominator) >= eps) {
sum += sign * numerator / denominator;
numerator *= x * x;
denominator += 2;
sign = -sign;
}
return sum;
}
int main() {
printf("%.10lf", 6 * arctanx(1.0 / sqrt(3)));
return 0;
}
1157：哥德巴赫猜想¶
提示 1：确定一个加数就确定另一个
要把偶数x拆成两个数，先选a，另一个只能是多少？
从小a往大试，找到的第一组有什么特点？
提示 2：两个加数都交给质数函数
放在枚举a的内层循环；外层x从6到100每次加2，break应结束哪一层？
知识补充
这里只验证题目指定的有限区间，不是证明哥德巴赫猜想对所有偶数成立。
常见错误
每个偶数只输出一次，不是输出全部拆分。
输出等号、加号时不加空格。
自测
无需输入，预期输出：
6=3+3
8=3+5
10=3+7
12=5+7
14=3+11
16=3+13
18=5+13
20=3+17
22=3+19
24=5+19
26=3+23
28=5+23
30=7+23
32=3+29
34=3+31
36=5+31
38=7+31
40=3+37
42=5+37
44=3+41
46=3+43
48=5+43
50=3+47
52=5+47
54=7+47
56=3+53
58=5+53
60=7+53
62=3+59
64=3+61
66=5+61
68=7+61
70=3+67
72=5+67
74=3+71
76=3+73
78=5+73
80=7+73
82=3+79
84=5+79
86=3+83
88=5+83
90=7+83
92=3+89
94=5+89
96=7+89
98=19+79
100=3+97
参考代码
#include <bits/stdc++.h>
using namespace std;
bool is_prime(int x) {
if (x < 2) return false;
for (int i = 2; i <= x / i; i++)
if (x % i == 0) return false;
return true;
}
int main() {
for (int x = 6; x <= 100; x += 2) {
for (int a = 2; a <= x / 2; a++) {
int b = x - a;
if (is_prime(a) && is_prime(b)) {
cout << x << '=' << a << '+' << b << '\n';
break;
}
}
}
return 0;
}
1397：简单算术表达式求值¶
提示 1：先让输入按类型自动分开
表达式12 +34含空格，也可以拆成整数、字符、整数。
提示 3：空格变化不应改变结果
把12+34、12 +34、12+ 34分别运行。
若用scanf，格式串"%d %c %d"中的空格也能跳过空白；%c自己不会跳过。
知识补充
scanf 的 %c 不会自动跳过空白，%d 会。
原来的 "%2d%c%2d" 可用于观察读取过程，但不满足本题全部输入条件。
例如 12 +34 会把空格读进运算符，不能因为某次测评通过就认定写法完整。
格式串 "%d %c %d" 中的空格会跳过空白，也允许那里没有空格。
%2d 只是限制最多读取两个字符宽度，不是读整数的必需写法。
常见错误
题面明确允许运算符前后有空格。
两位正整数相除是整数除法，输出结果不一定是两位数。
自测
输入：32+64 → 预期输出：96
输入：12 + 34 → 预期输出：46
输入：12+ 34 → 预期输出：46
输入：25 / 12 → 预期输出：2
输入：25 % 12 → 预期输出：1
输入：10-99 → 预期输出：-89
自己试试：自己写一个两位正整数的表达式，先算出结果。
只改变运算符两侧空格的数量，结果应不应该变？
方法一：cin 依次读取
方法二：scanf 跳过空白
方法三：字符串拆分（拓展）
#include <bits/stdc++.h>
using namespace std;
int to_number(string s) {
int value = 0;
for (int i = 0, len = s.size(); i < len; i++) value = value * 10 + s[i] - '0';
return value;
}
int main() {
string s, left, right;
getline(cin, s);
int pos = 0, len = (int)s.size();
while (pos < len && s[pos] == ' ') pos++;
while (pos < len && s[pos] >= '0' && s[pos] <= '9') left += s[pos++];
while (pos < len && s[pos] == ' ') pos++;
char op = s[pos++];
while (pos < len && s[pos] == ' ') pos++;
while (pos < len && s[pos] >= '0' && s[pos] <= '9') right += s[pos++];
int a = to_number(left), b = to_number(right);
if (op == '+') cout << a + b;
else if (op == '-') cout << a - b;
else if (op == '*') cout << a * b;
else if (op == '/') cout << a / b;
else if (op == '%') cout << a % b;
return 0;
}
1398：短信计费¶
提示 1：70字与71字差一条
每次发送要单独拆分，两次各35字是否只收一条的钱？
提示 2：让函数先返回整数条数
在int pieces(int x)中：
前半算整份，后半有剩余就加1；主函数先累计条数，最后除10.0换算元。
知识补充
每条 \(0.1\) 元，相当于把总条数除以 \(10\)。
pieces 把不足 \(70\) 字的剩余部分也算一条，不把不同次发送的内容合并。
常见错误
不是把所有次数的字数合起来再拆分。
避免反复累加 0.1，先统计整数条数更清楚。
自测
输入：3 70 71 140 → 预期输出：0.5
输入：1 1 → 预期输出：0.1
自己试试：自己造两次发送，让它们都刚好不超过一条短信。
如果把两次字数合并后计算，会不会得到不同费用？
参考代码
1399：甲流病人初筛¶
提示 1：温度和咳嗽要同时符合
体温38度但不咳嗽，能通过初筛吗？
再试恰好37.5且咳嗽的情况。
提示 2：让判断函数只返回真假
在bool check(double t, int cough)中：
主函数逐个读姓名与信息，通过时输出姓名并计数；人数最后再输出。
常见错误
没有人符合时，仍要输出人数 \(0\)。
用温度恰好 \(37.5\)、咳嗽标志为 \(0\) 的数据，检查“并且”有没有写错。
自测
输入：
预期输出：
输入：1 A 37.4 1 → 预期输出：0
参考代码
#include <bits/stdc++.h>
using namespace std;
bool check(double t, int cough) {
return t >= 37.5 && cough == 1;
}
int main() {
int n;
cin >> n;
int cnt = 0;
for (int i = 0; i < n; i++) {
string s;
double t;
int cough;
cin >> s >> t >> cough;
if (check(t, cough)) {
cout << s << '\n';
cnt++;
}
}
cout << cnt;
return 0;
}
1400：统计单词数¶
提示 1：先用一句短话分清整词
找to，在today to TO里应找到两次；先统一大小写。
位置从0数，空格也得占一格。
所以原句的空格别删，删了位置就变了。
提示 2：先找出一个词的两端
沿方法一写：i遇到空格就向后走，走到字母时用j找词尾。
len是原文长度，j从i开始：
此时text.substr(i, j - i)取出这个词；为什么先检查j < len？
提示 3：匹配一次，做两件事
word和text都已转成小写，cnt = 0、first = -1：
随后让i = j，回到循环继续找；后面再匹配时，只加次数，不改首次位置。
知识补充
get_lower 用引用参数修改原字符串。
find 找不到时返回 string::npos，不要先转成 int 再与 -1 比较。
方法二在两端补空格，把单词边界一起匹配；补入的首空格正好抵消匹配起点在单词前一个位置的偏移。
下一次从 pos + 1 查找，让相邻匹配仍能共用中间的空格。
常见错误
to 出现在 today 里不算一次匹配。
不能删掉原文空格再找位置，位置从 \(0\) 开始。
自测
输入：
预期输出：2 0
输入：
预期输出：2 6
输入：
预期输出：-1
输入：
预期输出：2 1
自己试试：自己造一句话，让目标单词连续出现两次，中间只隔一个空格。
只在句首加几个空格，次数和首次位置应该分别怎样变化？
方法一：逐个取出单词
#include <bits/stdc++.h>
using namespace std;
void get_lower(string &s) {
for (int i = 0, len = s.size(); i < len; i++)
if (s[i] >= 'A' && s[i] <= 'Z') s[i] += 'a' - 'A';
}
int main() {
string word, text;
getline(cin, word);
getline(cin, text);
get_lower(word);
get_lower(text);
int cnt = 0, first = -1;
int i = 0, len = (int)text.size();
while (i < len) {
if (text[i] == ' ') {
i++;
continue;
}
int j = i;
while (j < len && text[j] != ' ') j++;
if (text.substr(i, j - i) == word) {
cnt++;
if (first == -1) first = i;
}
i = j;
}
if (cnt == 0) cout << -1;
else cout << cnt << ' ' << first;
return 0;
}
方法二：补边界后使用 find
#include <bits/stdc++.h>
using namespace std;
void get_lower(string &s) {
for (int i = 0, len = s.size(); i < len; i++)
if (s[i] >= 'A' && s[i] <= 'Z') s[i] += 'a' - 'A';
}
int main() {
string word, text;
getline(cin, word);
getline(cin, text);
get_lower(word);
get_lower(text);
word = ' ' + word + ' ';
text = ' ' + text + ' ';
int cnt = 0;
string::size_type pos = text.find(word), first = pos;
while (pos != string::npos) {
cnt++;
pos = text.find(word, pos + 1);
}
if (cnt == 0) cout << -1;
else cout << cnt << ' ' << first;
return 0;
}
1401：机器翻译¶
提示 1：命中不会重新排队
容量2，依次处理1、2、1、3，最后该淘汰1还是2？
规则是最早进入内存的先出，不是最久没使用的先出。
知识补充
全局 vis 默认是 false，这里约定它表示“还不在内存中”。
这是人为建立的对应关系，不是 bool 自带的含义。
队列只在已满时取队头，题目给定容量为正数。
常见错误
命中也重新入队，会把先进先出误写成别的规则。
单词编号允许为 \(0\)，标记数组也要覆盖到 \(1000\)。
自测
输入：3 7 1 2 1 5 4 4 1 → 预期输出：5
输入：1 4 0 0 1 0 → 预期输出：3
输入：2 4 1 2 1 3 → 预期输出：3
自己试试：自己造一组单词，让最早进入内存的词刚被再次使用，接着就要淘汰一个词。
命中后如果错误地调整队列顺序，会淘汰谁？
参考代码
#include <bits/stdc++.h>
using namespace std;
queue<int> q;
bool vis[1010];
int main() {
int m, n;
cin >> m >> n;
int cnt = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (vis[x]) continue;
cnt++;
if ((int)q.size() == m) {
vis[q.front()] = false;
q.pop();
}
q.push(x);
vis[x] = true;
}
cout << cnt;
return 0;
}
1402：Vigenère 密码¶
提示 1：先试一个字母解密
密钥B代表偏移1，密文A往左移1要绕到哪个字母？
密钥大小写不改变偏移，明文大小写跟密文一致。
提示 3：解密减偏移，越界绕回
base是当前密文大小写对应的A或a：
先手算最左端减1的情况，检查加26的作用。
知识补充
密钥长度不超过 \(100\)，密文长度不超过 \(1000\)，输入只含英文字母。
i % k 使密钥下标循环回到开头。
这里的条件表达式 条件 ? 值一 : 值二 用于选择大写或小写起点。
常见错误
密钥大小写不影响偏移，明文大小写跟随密文。
求余前加 \(26\)，避免负余数导致字符越界。
自测
输入：CompleteVictory Yvqgpxaimmklongnzfwpvxmniytm → 预期输出：Wherethereisawillthereisaway
输入：abc Hfnlpyosnd → 预期输出：Helloworld
输入：B Aa → 预期输出：Zz
自己试试：自己选一个带大小写字母的密文，用同一个密钥解密。
只改变密钥的大小写，结果应不应该变？
参考代码
#include <bits/stdc++.h>
using namespace std;
int shift(char c) {
if (c >= 'a' && c <= 'z') return c - 'a';
return c - 'A';
}
int main() {
string key, cipher;
cin >> key >> cipher;
string ans;
int k = (int)key.size();
for (int i = 0, len = cipher.size(); i < len; i++) {
int d = shift(key[i % k]);
char base = cipher[i] >= 'a' && cipher[i] <= 'z' ? 'a' : 'A';
ans += (char)(base + (cipher[i] - base - d + 26) % 26);
}
cout << ans;
return 0;
}
1403：素数对¶
提示 1：相差2就不必再枚举第二个
较小数i确定，较大数是i加2，两个都不能超过n。
提示 2：复用两次质数判断
先写好is_prime，主函数循环：
找到时输出并做标记，但不要break，3与5、5与7都应保留。
提示 3：最后才决定是否empty
标记初值false，有一对就设true；循环结束仍为false，才输出empty。
知识补充
本题 \(n\le10000\)，数组容量要包含下标 \(10000\)。
筛法中的 true 约定为“不是质数”，所以要把 \(0\)、\(1\) 单独标记。
常见错误
两个数都必须不超过 \(n\)。
\(3,5\) 与 \(5,7\) 是不同的两对，不能跳过共享的质数。
方法一：调用质数判断函数
#include <bits/stdc++.h>
using namespace std;
bool is_prime(int x) {
if (x < 2) return false;
for (int i = 2; i <= x / i; i++)
if (x % i == 0) return false;
return true;
}
int main() {
int n;
cin >> n;
bool found = false;
for (int i = 2; i + 2 <= n; i++) {
if (is_prime(i) && is_prime(i + 2)) {
cout << i << ' ' << i + 2 << '\n';
found = true;
}
}
if (!found) cout << "empty";
return 0;
}
方法二：筛法预处理
#include <bits/stdc++.h>
using namespace std;
bool st[10010];
void get_primes(int n) {
st[0] = st[1] = true;
for (int i = 2; i <= n; i++) {
if (st[i]) continue;
for (int j = i + i; j <= n; j += i) st[j] = true;
}
}
int main() {
int n;
cin >> n;
get_primes(n);
bool found = false;
for (int i = 2; i + 2 <= n; i++) {
if (!st[i] && !st[i + 2]) {
cout << i << ' ' << i + 2 << '\n';
found = true;
}
}
if (!found) cout << "empty";
return 0;
}
1404：我家的门牌号¶
提示 1：先假设有4家
门牌是1、2、3、4，总和为10。
假设我家是3号，其余各家合计7，再减去我家门牌号的两倍，得到\(7-2\times3=1\)。
先按题意算一次，不急着把式子合并。
提示 2：户数和门牌号，分两层试
沿方法一写：外层用y枚举总户数，内层用x枚举我家门牌号，从1试到y。
sum记录1到y的门牌总和，y每增加1，就给sum加上这个新门牌号。
固定一组x、y后，先算其余各家的总和：
接着检查other - 2 * x是否等于输入的n，把这句判断补进去。
提示 3：找到后，两层都要停
题目保证唯一解，找到就按“我家门牌号、总户数”的顺序输出。
这里写在main中，输出后用return 0;结束程序；只写break会退出哪一层？
知识补充：为什么不需要很大的范围
若有450家，门牌总和为101475，即使我家是最大的450号，差值也有\(101475-3\times450=100125\)。
户数继续增加，这个最小差值还会增加，已超过题目的\(n<100000\)。
所以合法解的总户数不到450，两层枚举最多检查约十万次，int也足够。
常见错误
sum包含我家的门牌号，先减掉一次，才是“其余各家”。
内层的x只能从1到y，不能试一个胡同里不存在的门牌号。
sum在外层每增加一家时更新，别在尝试每个x时重复累加。
自测
输入：100 → 预期输出：12 16
输入：1 → 预期输出：3 4
输入：99997 → 预期输出：193 448
自己试试：用输出的两个数，还原“门牌总和、其余各家总和、减去两倍我家”的过程。
看最后能否回到输入的n。
方法一：枚举户数和我家门牌号
先用两层循环按题意检查，不需要先反求x。
方法二：列式后只枚举户数（拓展）
sum - x - 2 * x = n，合并后是sum - 3 * x = n。
因此固定y后，x = (sum - n) / 3，不用再试每个门牌号。
要先确认能被3整除，再检查x在1到y之间；下面用t保存sum - n。
1405：质数的和与积¶
提示 1：和固定，但两数还必须是质数
和为10时，2与8虽然能相加到10，能用吗？
提示 2：确定a，再检查剩下的数
输入和s，ans从0开始，a从2试到s / 2：
自己补循环；为什么要允许两数相等，例如2与2？
知识补充
\(s\le10000\)，最大乘积不超过 \(25000000\)，int 足够。
常见错误
两个质数可以相同，例如 \(4=2+2\)。
本题保证有解，不需要自定义无解输出。
自测
输入：50 → 预期输出：589
输入：4 → 预期输出：4
输入：10 → 预期输出：25
参考代码
#include <bits/stdc++.h>
using namespace std;
bool is_prime(int x) {
if (x < 2) return false;
for (int i = 2; i <= x / i; i++)
if (x % i == 0) return false;
return true;
}
int main() {
int s;
cin >> s;
int ans = 0;
for (int a = 2; a <= s / 2; a++)
if (is_prime(a) && is_prime(s - a)) ans = max(ans, a * (s - a));
cout << ans;
return 0;
}
1406：单词替换¶
提示 1：先分词，不直接替换片段
句子cat scatter cat，只换独立单词cat，scatter里面要动吗？
提示 2：找到词尾再比较
s是原句，i指词首，j从i走到空格或末尾，目标为a，新词为b：
输出词后处理分隔空格，再移到下一词；用只有一个词的句子检查末尾。
知识补充
题面规定单词间恰好一个空格，三行输入首尾没有空格。
这里先整行读取句子，再读两个单词。
常见错误
You 和 you 不相同。
循环先检查下标，再访问字符，最后一个单词也要处理。
自测
输入：
预期输出：I want someone to help you
输入：
预期输出：dog scatter dog
输入：
预期输出：b
自己试试：自己造一句话，让目标词既独立出现，也藏在别的单词里。
只改一个独立单词的大小写，替换结果应怎样变化？
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
string s, a, b;
getline(cin, s);
cin >> a >> b;
for (int i = 0, len = s.size(); i < len; ) {
int j = i;
while (j < len && s[j] != ' ') j++;
string word = s.substr(i, j - i);
if (word == a) cout << b;
else cout << word;
if (j < len) cout << ' ';
i = j + 1;
}
return 0;
}
1407：笨小猴¶
提示 1：没出现的字母不参加最少次数
error里e、r、o各出现几次？
其他字母的0次不能拿来当最少。
提示 3：不是质数时输出的不是差
差为0或1都不是质数，第二行要输出0。
分别用error、a检查两类输出文字。
常见错误
差为 \(0\) 或 \(1\) 时都不是质数。
不是幸运单词时，第二行输出 \(0\)，不是直接输出差值。
参考代码
#include <bits/stdc++.h>
using namespace std;
int cnt[26];
bool is_prime(int x) {
if (x < 2) return false;
for (int i = 2; i <= x / i; i++)
if (x % i == 0) return false;
return true;
}
int main() {
string s;
cin >> s;
for (int i = 0, len = s.size(); i < len; i++) cnt[s[i] - 'a']++;
int maxn = 0, minn = 100;
for (int i = 0; i < 26; i++) {
if (cnt[i] == 0) continue;
maxn = max(maxn, cnt[i]);
minn = min(minn, cnt[i]);
}
int d = maxn - minn;
if (is_prime(d)) cout << "Lucky Word" << '\n' << d;
else cout << "No Answer" << '\n' << 0;
return 0;
}
1408：系数回文数的个数¶
提示 1：范围与结果都和前题不同
只检查从11到n的数，这次输出个数而不是名单。
提示 2：两个函数给出两道检查
cnt从0开始，已有is_prime和reverse_num：
放进11到n的循环；别把单个数字的质数也加进去。
知识补充
输入满足 \(11<n<1000\)。
标题沿用原页，实际统计对象以题面为准：既是质数又是回文数。
常见错误
不能把个位质数也算进去。
不要用“跳过前几个质数”代替清楚的数值范围。
自测
输入：23 → 预期输出：1
输入：12 → 预期输出：1
输入：999 → 预期输出：16
参考代码
#include <bits/stdc++.h>
using namespace std;
bool is_prime(int x) {
if (x < 2) return false;
for (int i = 2; i <= x / i; i++)
if (x % i == 0) return false;
return true;
}
int reverse_num(int x) {
int t = 0;
while (x) {
t = t * 10 + x % 10;
x /= 10;
}
return t;
}
int main() {
int n;
cin >> n;
int cnt = 0;
for (int i = 11; i <= n; i++)
if (is_prime(i) && reverse_num(i) == i) cnt++;
cout << cnt;
return 0;
}
1409：判决素数个数¶
提示 1：两个端点可能反着给
输入10和2时，与输入2和10的区间是不是一样？
知识补充
两种方法都覆盖 \(1\le X,Y\le10^5\)。
筛法先处理到较大端点，之后每个数只查一次标记。
方法三保留线性筛的写法，每个合数只由最小质因子筛掉一次，可以学过筛法后再看。
常见错误
两个端点都包含，\(1\) 不能计为质数。
数组下标必须小于容量，不能对容量本身做筛选。
自测
输入：1 100 → 预期输出：25
输入：10 2 → 预期输出：4
输入：1 1 → 预期输出：0
输入：99991 100000 → 预期输出：1
自己试试：自己选两个不同的合法端点，先数出区间里的质数。
只交换输入顺序，答案应不应该变？
方法一：逐个试除判断
#include <bits/stdc++.h>
using namespace std;
bool is_prime(int x) {
if (x < 2) return false;
for (int i = 2; i <= x / i; i++)
if (x % i == 0) return false;
return true;
}
int main() {
int x, y;
cin >> x >> y;
if (x > y) swap(x, y);
int cnt = 0;
for (int i = x; i <= y; i++)
if (is_prime(i)) cnt++;
cout << cnt;
return 0;
}
方法二：筛法预处理
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 10;
bool st[N];
void get_primes(int n) {
st[0] = st[1] = true;
for (int i = 2; i <= n; i++) {
if (st[i]) continue;
for (int j = i + i; j <= n; j += i) st[j] = true;
}
}
int main() {
int x, y;
cin >> x >> y;
if (x > y) swap(x, y);
get_primes(y);
int cnt = 0;
for (int i = x; i <= y; i++)
if (!st[i]) cnt++;
cout << cnt;
return 0;
}
方法三：线性筛预处理（拓展）
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 10;
bool st[N];
int primes[N], idx;
void get_primes(int n) {
st[0] = st[1] = true;
for (int i = 2; i <= n; i++) {
if (!st[i]) primes[idx++] = i;
for (int j = 0; j < idx && primes[j] <= n / i; j++) {
st[i * primes[j]] = true;
if (i % primes[j] == 0) break;
}
}
}
int main() {
int x, y;
cin >> x >> y;
if (x > y) swap(x, y);
get_primes(y);
int cnt = 0;
for (int i = x; i <= y; i++)
if (!st[i]) cnt++;
cout << cnt;
return 0;
}
1410：最大质因子序列¶
提示 1：一个因数可能要除很多遍
把72按从小到大试除，2要除几次才除尽？
用函数largest_factor单独求一个数的最大质因子。
提示 2：除掉当前因数再接着试
函数参数x是副本，候选i从2开始，ans初值1：
i只需试到i <= x / i；最后x还大于1时，它也是剩下的质因子。
提示 3：主函数负责范围和逗号
逐个调用函数；第二项起才在前面加逗号，别在末尾补逗号。
知识补充
本题 \(1<m<n\le5000\)。
质数输入时没有小因子能除掉它，最后返回它本身。
常见错误
不能只除一次，例如 \(8\) 要连续除去三个 \(2\)。
逗号只放在两项之间，这里需要分隔控制。
自测
输入：5 10 → 预期输出：5,3,7,2,3,5
输入：2 4 → 预期输出：2,3,2
输入：48 49 → 预期输出：3,7
参考代码
#include <bits/stdc++.h>
using namespace std;
int largest_factor(int x) {
int ans = 1;
for (int i = 2; i <= x / i; i++) {
while (x % i == 0) {
ans = i;
x /= i;
}
}
if (x > 1) ans = x;
return ans;
}
int main() {
int m, n;
cin >> m >> n;
for (int i = m; i <= n; i++) {
if (i > m) cout << ',';
cout << largest_factor(i);
}
return 0;
}
1411：区间内的真素数¶
提示 1：反过来仍要是质数
13在区间内，反序31不在区间内，是否影响13成为真素数？
这里范围管的是原来的数，倒过来的数，只检查它是不是质数。
提示 2：拼起两个现成函数
i在m到n之间：
保留逗号分隔控制；循环全部结束仍没找到才输出No。
知识补充
原数不超过 \(100000\)，反序结果也不会超过 \(100000\)，筛表可覆盖两者。
筛表中的 true 表示“不是质数”，包含 \(0\) 和 \(1\)。
常见错误
反序时可以丢掉前导零，但 \(1\) 仍不是质数。
没有符合项时输出 No，有结果时用逗号分隔。
自测
输入：10 35 → 预期输出：11,13,17,31
输入：1 1 → 预期输出：No
输入：13 13 → 预期输出：13
输入：100000 100000 → 预期输出：No
方法一：逐个试除判断
#include <bits/stdc++.h>
using namespace std;
bool is_prime(int x) {
if (x < 2) return false;
for (int i = 2; i <= x / i; i++)
if (x % i == 0) return false;
return true;
}
int reverse_num(int x) {
int t = 0;
while (x) {
t = t * 10 + x % 10;
x /= 10;
}
return t;
}
int main() {
int m, n;
cin >> m >> n;
bool found = false;
for (int i = m; i <= n; i++) {
if (is_prime(i) && is_prime(reverse_num(i))) {
if (found) cout << ',';
cout << i;
found = true;
}
}
if (!found) cout << "No";
return 0;
}
方法二：筛法预处理
#include <bits/stdc++.h>
using namespace std;
bool st[100000 + 10];
void get_primes(int n) {
st[0] = st[1] = true;
for (int i = 2; i <= n; i++) {
if (st[i]) continue;
for (int j = i + i; j <= n; j += i) st[j] = true;
}
}
int reverse_num(int x) {
int t = 0;
while (x) {
t = t * 10 + x % 10;
x /= 10;
}
return t;
}
int main() {
int m, n;
cin >> m >> n;
get_primes(100000);
bool found = false;
for (int i = m; i <= n; i++) {
if (!st[i] && !st[reverse_num(i)]) {
if (found) cout << ',';
cout << i;
found = true;
}
}
if (!found) cout << "No";
return 0;
}
1412：二进制分类¶
提示 1：只数有效二进制位
10的二进制为1010，1与0一样多，按题面属于哪类？
不能把整数存储时前面补的零也数进去。
提示 2：除2的余数就是当前一位
在check(x)中one、zero从0开始：
函数返回one > zero，主函数枚举1到1000分别计入两类。
常见错误
两种数字一样多时归入 B 类。
不要把固定整数类型里补齐的前导零也统计进去。
自测
无需输入，预期输出：538 462
方法一：除以 2 统计数位
方法二：按位检查（拓展）
#include <bits/stdc++.h>
using namespace std;
bool check(int x) {
int one = 0, bits = 0;
for (int j = 0; (1 << j) <= x; j++) {
if (x & (1 << j)) one++;
bits++;
}
return one > bits - one;
}
int main() {
int a = 0, b = 0;
for (int i = 1; i <= 1000; i++) {
if (check(i)) a++;
else b++;
}
cout << a << ' ' << b;
return 0;
}
1413：确定进制¶
提示 1：纸上的42不一定是四十二
在13进制里，42表示4乘13加2，等于多少？
先别直接用输入的p、q、r做十进制乘法。
提示 2：从低位累加各位贡献
value(x, base)中sum从0、weight从1开始，每次取d = x % 10：
比如二进制里能不能出现数字2？先用这个想一下。
函数返回值用long long。
提示 3：从小进制试，避免乘积溢出
主函数从2到40试base，三次value得到a、b、c，非法值先跳过。
三个转换值为正，这样比较不必计算可能溢出的a乘b。
知识补充
输入 \(p,q,r\) 在 \(1\) 到 \(10^6\) 之间，它们的十进制写法用于保存数位。
value 返回 -1，表示当前进制下存在非法数位。
转换结果为正数，可以用 c % a == 0 && c / a == b 代替乘法等式，避免乘积溢出。
拿 \(42\)、进制 \(13\) 跟一遍 x、weight、sum 的变化，再关上提示自己写。
常见错误
某一位不小于进制时，这个进制不合法。
转换后的数能放进 long long，它们的乘积却不一定能。
自测
输入：6 9 42 → 预期输出：13
输入：11 11 121 → 预期输出：3
输入：1 1 1 → 预期输出：2
输入：1 1 2 → 预期输出：0
输入：1000000 1000000 1 → 预期输出：0
自己试试：自己选一个小进制，写出一组只含数字的乘法等式。
这是否就是最小可行进制，还要怎样检查？
参考代码
#include <bits/stdc++.h>
using namespace std;
long long value(int x, int base) {
long long sum = 0, weight = 1;
do {
int d = x % 10;
if (d >= base) return -1;
sum += d * weight;
weight *= base;
x /= 10;
} while (x);
return sum;
}
int main() {
int p, q, r;
cin >> p >> q >> r;
int ans = 0;
for (int base = 2; base <= 40; base++) {
long long a = value(p, base), b = value(q, base), c = value(r, base);
if (a == -1 || b == -1 || c == -1) continue;
if (c % a == 0 && c / a == b) {
ans = base;
break;
}
}
cout << ans;
return 0;
}
第二节 递归算法¶
1158：求 1+2+3+…¶
提示 2：调用下去，还要一层层返回
剩下的情况，就写return f(n - 1) + n;。
求f(3)时，先等f(2)；f(2)又先等f(1)。
f(1)返回1后，f(2)得到3，f(3)再得到6。
f(4)你来走一遍，每一层只加回自己的那个数，别一下跳到答案。
知识补充
函数返回值用 long long，避免总和先在 int 中溢出。
题面未给出 \(n\) 上界，递归深度随 \(n\) 增长，不能把这种教学写法当作任意大输入的通用实现。
常见错误
没有终止条件，就会一直往下调用。
返回的是子问题的结果加 \(n\)，不能忘掉 return。
自测
输入：5 → 预期输出：15
输入：1 → 预期输出：1
输入：100 → 预期输出：5050
参考代码
1159：斐波那契数列¶
提示 1：先对齐项号
第1项是0，第2项是1；先在纸上写出前五项。
函数f(n)返回的是第n项的值，不是前n项的和。
提示 2：两项能直接回答，其余接着问
在long long f(int n)中先写：
其余返回f(n - 1) + f(n - 2)；自己用第3项检查开头是否接对。
提示 3：同一个问题被问了几次
求f(5)要算f(4)和f(3)，而f(4)又要算一次f(3)。
你看，f(3)又算了一遍。
在草稿上把这两处圈一下，这就是重复计算。
先拿前几项，把递归走一遍。
记忆化先不着急，等你看出哪儿重复了，再往下看。
知识补充
直接递归会反复计算相同项，项号变大时会很慢。
拓展方法把算过的项存起来，每项只展开一次，可以以后再看。
memo.assign(n + 1, -1) 分配存储空间并填入 -1，这里约定它表示“尚未计算”。
题面未给项号上界；long long 可容纳到第 \(93\) 项，第 \(94\) 项起需更大的整数表示，不表示直接递归能快速算到第 \(93\) 项。
常见错误
第 \(1\) 项是 \(0\)，不是 \(1\)。
不能用零表示“没有算过”，因为合法答案本来就可能是零。
自测
输入：3 → 预期输出：1
输入：1 → 预期输出：0
输入：2 → 预期输出：1
输入：30 → 预期输出：514229
自己试试：自己选相邻的三个小项号，先手算结果。
它们应满足什么关系，能帮你检查起点有没有写错？
方法一：按定义递归
先用小的项号观察调用过程；这份写法有重复计算，数值增大后会很慢。
方法二：记忆化（拓展）
1160：倒数数¶
提示 1：先输出个位会怎样
123先输出3，再处理12，会得到什么顺序？
函数只负责输出，所以返回类型用void。
提示 2：数位处理完就结束当前调用
把片段放进void f(long long n)；输入7时，一共输出几次？
知识补充
void 函数不返回计算值，这里用它完成输出。
return; 表示结束当前这一次调用。
常见错误
本题给定个位不为零，不需要自己添加保留整数前导零的规则。
输出放在递归调用前后，顺序不同。
自测
输入：123 → 预期输出：321
输入：7 → 预期输出：7
输入：10203 → 预期输出：30201
参考代码
1161：转进制¶
提示 1：余数先得到的是低位
把10反复除以2，余数顺序是0、1、0、1，直接按这个顺序输出对吗？
提示 2：先递归处理商，再输出余数
进制保存在base，digit为"0123456789ABCDEF"：
放进convert函数；从10到0，再返回时逐个写出输出顺序。
提示 3：输入零与递归结束分开
主函数n为0时直接输出一个0；否则调用convert。
为何不能在函数每次x等于0时都输出0？
知识补充
进制按定义至少为 \(2\)，本题转换到不超过 \(16\) 的进制。
digit 的下标是余数，对应要输出的数字或字母。
常见错误
十六进制中 \(10\) 到 \(15\) 要输出 A 到 F。
不能把零和“递归已经没有更多高位”混成一种输出。
自测
输入：31 16 → 预期输出：1F
输入：10 2 → 预期输出：1010
输入：0 16 → 预期输出：0
自己试试：自己选一个小整数，先把它写成二进制和十六进制。
分别按位还原成十进制，是否回到原数？
参考代码
1162：字符串逆序¶
提示 2：下标每次少一个
在void f(const string &s, int pos)中先处理：
再输出s[pos]并调用f(s, pos - 1)，先检查再访问；主函数从最后一个下标调用。
知识补充
getline(cin, s, '!') 读到半角 ! 为止，空格也会保留，但 ! 不存入字符串。
因此最后一个字符的下标是 len - 1，不用再跳过结束符。
const string &s 让递归共用原字符串，不在每次调用时复制，也不在函数中修改它。
递归深度随字符数增长，题面未给长度上界，仍需注意调用层数。
常见错误
cin >> s 遇到空格就停止，输入 a b! 时不能读到完整内容。
当前读法没有把 ! 存进字符串，再从 len - 2 开始会漏掉最后一个字符。
先判断 pos < 0，再访问 s[pos]，避免下标越界。
自测
输入：abc! → 预期输出：cba
输入：a b! → 预期输出：b a
输入：x! → 预期输出：x
自己试试：自己写一串带空格、以 ! 结束的字符，先在纸上反序。
只在结束符前增加一个空格，输出应在哪个位置多一个空格？
参考代码
1163：阿克曼 (Ackermann) 函数¶
提示 1：先挑能直接算的情况
按定义，\(A(0,2)=3\)。
再算\(A(1,0)=A(0,1)\)，用第一条定义得到结果。
提示 2：先把这两种情况写好
放在ack函数的前面：
用刚才手算的两组数检查，再写后面的情况。
提示 3：先算里面，拿结果交给外面
\(A(1,1)=A(0,A(1,0))\)，里面的\(A(1,0)\)等于2，所以外面变成\(A(0,2)\)。
代码对应ack(m - 1, ack(m, n - 1))。
再算一下\(A(1,2)\)。
留意啊，里面算出的结果，是交给外面的函数接着算，不是两个答案相加。
知识补充
题目限定 \(0\le m\le3\)、\(0\le n\le10\)。
手算 \(A(1,1)\) 时，先写出最里面的 \(A(1,0)\)，不要一口气把所有层都展开。
常见错误
别把嵌套调用改成两个函数值相加。
\(m=0\) 时直接返回，不再进入其他分支。
自测
输入：2 3 → 预期输出：9
输入：0 10 → 预期输出：11
输入：3 0 → 预期输出：5
输入：3 4 → 预期输出：125
参考代码
1164：digit 函数¶
提示 1：去掉个位后，位置也变了
31859从右数第3位是8，去掉9以后，它是新数的第几位？
提示 2：两个参数一起缩小
在digit(n,k)中先写：
其余情况返回digit(n / 10, k - 1)；只减少k而不除n，会一直看到哪一位？
常见错误
这里是从右数，不是从左数。
\(n\) 和 \(k\) 要一起更新，只改其中一个会找错位置。
自测
输入：31859 3 → 预期输出：8
输入：10203 2 → 预期输出：0
输入：7 1 → 预期输出：7
自己试试：自己选一个中间带零的正整数，再指定这个零的位置。
把 \(k\) 增加或减少 \(1\)，预期应取出哪一个数字？
参考代码
1165：Hermite 多项式¶
提示 1：先只算第二阶
固定\(x=2\)，先算出\(h_0(2)=1\)、\(h_1(2)=4\)。
代入题面的下一条公式，\(h_2(2)=2\times2\times4-2\times1\times1=14\)。
提示 2：先写能直接回答的两阶
在double h(int n, double x)中：
其余把公式里的前两阶换成h(n - 1, x)、h(n - 2, x)。
系数仍是2 * (n - 1)，自己补完整表达式，再用刚才的14核对。
提示 3：每层只改变阶数
求\(h_3(2)\)时，仍用同一个\(x=2\)，只去求前两阶。
若研究后面的记忆化，先圈出重复求过的阶数；用vis记是否算过，不能拿函数值0作标记。
知识补充
题目给出的定义是
记忆化把已经算过的值保存下来，再次遇到相同问题时直接取用，可以以后再看。
同一次计算中 \(x\) 不变，所以只需按阶数 \(n\) 保存结果。
vis[n] 记录是否计算过，memo[n] 才是函数值。
题面输出说明未写位数，但原题样例为 4.00，这里沿用两位小数格式。
辅助数组放在全局，vis 默认是 false，表示还没有计算。
本实现预留 \(100010\) 个位置，可使用下标 \(0\) 到 \(100009\)，这不是题面给出的阶数上界。
题面未给阶数上界，使用时仍需检查数组容量、递归深度和浮点数范围。
常见错误
公式中的系数是 \(2(n-1)\)，不是 \(2n\)。
函数值可能为零或负数，要用独立标记表示“算过”。
自测
输入：1 2 → 预期输出：4.00
输入：2 1 → 预期输出：2.00
输入：3 2 → 预期输出：40.00
输入：4 1 → 预期输出：-20.00
方法一：按定义递归
先用小的阶数观察调用过程；这份写法有重复计算，数值增大后会很慢。
方法二：记忆化（拓展）
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
double memo[N];
bool vis[N];
double h(int n, double x) {
if (n == 0) return 1;
if (n == 1) return 2 * x;
if (vis[n]) return memo[n];
memo[n] = 2 * x * h(n - 1, x) - 2 * (n - 1) * h(n - 2, x);
vis[n] = true;
return memo[n];
}
int main() {
int n;
double x;
cin >> n >> x;
printf("%.2lf", h(n, x));
return 0;
}
1166：求 f (x,n)¶
提示 1：从最外层根号往里看
先写n为2的式子，最外面是根号下2加上哪一个更小结果？
提示 2：最里层直接计算
在f(x,n)中：
其他层用return sqrt(n + f(x, n - 1));；每层的n会变化，x在哪一层真正参与加法？
知识补充
题面中的 \(4.2,10\) 与 \(2.5,15\) 是两组计算示例，程序仍应读取输入。
根式中的每个 \(n\) 对应当前递归层，不是一直使用最初的项号。
常见错误
读入顺序是 \(x,n\)。
不要把 \(x\) 加到每一层，只有最里层含它。
自测
输入：4.2 10 → 预期输出：3.68
输入：2.5 15 → 预期输出：4.39
输入：3 1 → 预期输出：2.00
参考代码
1167：再求 f (x,n)¶
提示 1：把分母看成一个整体
先用x为1写出n为1、n为2的连分式，不能把它拆成两项相加。
提示 2：先求内层，再放进分母
在f(x,n)中：
其他层返回x / (n + f(x, n - 1))；x为1、n为2时，先算二分之一，再代入外层。
知识补充
原题图片中的连分式可写成
例如 \(x=1,n=2\) 时，先算内层 \(\frac12\)，再算 \(\frac1{2+\frac12}=0.4\)。
常见错误
每一层的分子都是 \(x\)，分母是当前 \(n\) 加上内层结果。
用 double 计算，按原题样例保留两位小数。
自测
输入：1 2 → 预期输出：0.40
输入：2 2 → 预期输出：0.75
输入：1 1 → 预期输出：0.50