约瑟夫环与回文质数：C语言循环边界和取模运算实战解析

刷题刷到第8天，我的任务单上是三道看起来完全不沾边、实际上处处相通的老题：约瑟夫环、整除的尾数、回文质数。今天特别想聊这组题，是因为约瑟夫环做到了“2”这个进阶版本——双向跳跃，也就是顺时针走几步、逆时针走几步交替淘汰，比经典的单向绕圈麻烦不少。我把整组题的完整思路、可运行代码、测试结果和踩坑记录都整理在下面。

这篇东西适合刚学完数组和循环、想找点综合题练手的人，也适合准备机试但基础还不牢的人。三道题都不算难，但如果你能把这它们一次性写对，说明你对循环边界、取模运算和判定顺序已经有一定的直觉。文章里的代码我全部用C语言写，注释直接放在关键行旁边，方便你照着敲一遍。

1. 三道题的组合逻辑与day8的训练目标

1.1 为什么是三题连刷：模拟、枚举、判断三种基本功

如果只看题名，你会觉得这像是随机拼凑的练习。但实际做下来，它们分别考察的是三类编程基本功，恰好能形成互补。

约瑟夫环练的是状态模拟。你要在内存里维护一个“人还在不在圈子”的状态，然后用循环去模拟报数过程。这种能力在做游戏逻辑、消息队列、任务调度时都会用到。整除的尾数练的是枚举和取模，核心是把“添加几位数字”翻译成数学表达式，再通过余数快速筛选。回文质数练的是判定逻辑和剪枝顺序，什么时候该先判断回文、什么时候该先生成回文，选择不同，运行时间可能差出几百倍。

这三个题还有一个共同点：都在反复敲打同一个知识点——循环边界。约瑟夫环要处理环形下标越界，整除尾数要处理枚举范围，回文质数要处理质数判定里的平方根边界。一个循环边界写错，整道题全废。所以day8的安排看起来零散，实际是很典型的“基础边界训练日”。

1.2 我做这类题的顺序习惯：先模拟跑通，再谈优化

很多人一上来就想用数学公式秒杀约瑟夫环，或者先写一个高大上的筛法做回文质数。我的建议恰恰相反：先在能力范围内写最笨、最直接的版本，让它跑出正确结果，再回头优化。

理由很简单。第一，笨版本逻辑简单，出错容易定位。第二，你先知道正确答案长什么样，优化版本写错时才知道哪里错了。比如约瑟夫环，如果你第一版就用递推公式，公式本身没错，但你要是把下标初始值写错，根本没法用普通调试思路去查，因为中间过程完全不可见。先做数组模拟，把淘汰顺序打印出来，你心里就有了底。

这决定了后面每个题我都会给出“朴素版”和“优化版”两套思路，而不是直接甩最优解。

2. 约瑟夫环：经典模型与双向跳跃新变种

2.1 经典约瑟夫环的数组模拟写法

先看最常见的基础题：n个人围成一圈，编号从1到n，从1号开始报数，每次数到m的人出圈，问最后剩下几号。

经典的数组模拟思路是开一个标记数组，0表示还在圈里，1表示已经出圈。用一个变量cur表示“报数人前一个位置”，然后循环数到m个人。为什么是“前一个位置”？因为要把起点对准1号，避免从0号开始数出一步偏移。

int survivor(int n, int m) { int a[10005] = {0}; // 0在圈中，1已淘汰 int cur = n - 1; // 指向1号前一个位置 int left = n; while (left > 1) { int cnt = 0; while (cnt < m) { // 连续移动m次 cur = (cur + 1) % n; if (a[cur] == 0) cnt++; // 只数还在圈里的人 } a[cur] = 1; left--; } for (int i = 0; i < n; i++) { if (a[i] == 0) return i + 1; // 编号 = 下标 + 1 } return -1; }

验证一下：n=5、m=3，第一轮下标从4开始移动，落点是下标2，也就是3号出圈。第二轮从下标2继续移动，跳过已出圈的人，依次淘汰1号、5号、2号，最后剩下4号。这个结果和手算一致。

这个写法的复杂度是O(n*m)，n到几千都没问题。注意数组要开成至少n+1，很多人只开a[1000]但输入n=1000，下标越界查半天。

2.2 报数方向的本质：下标移动与取模

不管是顺时针还是逆时针，本质都是在处理“循环取模”：

next = (cur + dir + n) % n;

dir为1表示顺时针，dir为-1表示逆时针。这里的+n不是多余的，它是C语言负数取模的救星。-1 % 5在C语言里结果是-1，直接拿去做数组下标就是越界；(-1 + 5) % 5得到4，正好从0号位置逆时针绕到末尾。这个写法建议直接背下来，后面约瑟夫环变种、双端轮询、环形缓冲区都能用。

很多人写顺时针时用(cur + 1) % n，一旦要支持逆时针，就把(cur - 1) % n直接搬过来，结果下标变成负数。这个问题我踩过不止一次，尤其是当cur从0开始逆时针移动时，必出负号。所以统一写成(cur + dir + n) % n最稳，dir取1或-1，再配合三元表达式判断方向。

2.3 双向跳跃约瑟夫环：方向切换和起点重置

约瑟夫环2的常见变种是“双向跳跃”：n个人围成一圈，第一轮从1号开始顺时针走a步，淘汰落在的人；然后从淘汰位置沿当前方向找下一个仍在圈里的人作为新起点，第二轮到逆时针走b步，淘汰落在的人；之后方向交替、步数keep切换。换句话说，奇数次顺时针走a，偶数次逆时针走b。

这个变种的难点有三个。

第一，“走a步”的定义要读清楚。有的题面是“从当前点出发，移动a次后落在哪里”，有的题面是“从当前人开始报数，数到第a个人”。我把代码写成前者，如果你想按后者来，只要把循环次数从step改成step-1。差一问题在这里特别容易发生。

第二，方向和步数必须同步切换。方向从顺时针翻到逆时针时，下一步的步数要换到b，不是继续用a。很多人的代码第一次淘汰正常，第二轮就全乱了，十有八九是方向变了但step忘了变。

第三，出圈后起点要重新定位。淘汰一个人之后，不能直接拿被淘汰的位置当下一轮起点，必须沿着当前方向往前走，找到下一个仍在圈里的位置。这个步骤如果漏了，后面数人的时候会把已淘汰的人也算进去。

2.4 双向跳跃变种的完整代码与测试

下面这段是我调试通过的完整版本：

#include <stdio.h> int main() { int n = 5; // 人数 int a = 2; // 顺时针走2步 int b = 3; // 逆时针走3步 int people[100] = {0}; // 0在场，1已出圈 int cur = 0; // 当前起点下标，对应编号1 int direction = 1; // 1顺时针，0逆时针 int step = a; int outCnt = 0; printf("出圈顺序："); while (outCnt < n) { // 从当前点出发，走step步，每步必须落在未出圈的人身上 for (int i = 0; i < step; ) { cur = (cur + (direction ? 1 : -1) + n) % n; if (!people[cur]) i++; } people[cur] = 1; outCnt++; printf("%d%c", cur + 1, outCnt == n ? '\n' : ' '); if (outCnt == n) break; // 沿当前方向寻找下一个仍在场的人作为新起点 while (1) { cur = (cur + (direction ? 1 : -1) + n) % n; if (!people[cur]) break; } // 方向取反，步数同步切换 direction = !direction; step = direction ? a : b; } return 0; }

n=5、a=2、b=3时，我的运行结果如下：

出圈顺序：3 5 2 1 4

你可以手动推一遍第一轮验证逻辑：从1号出发，顺时针走两步，第一部落到2号，第二部落到3号，所以3号淘汰。然后从3号位置沿顺时针方向找到4号作为新起点，方向切到逆时针，步数切到3，继续淘汰。完整过程跑下来没有任何一步落在空位上。

这个版本的复杂度是O(n×平均步数)，数组标记法在n小于几千时非常好用。如果题目只问最后幸存者，可以用数学递推f[i] = (f[i-1] + m) % i做到O(n)，但那种写法只能算最后编号，不能输出淘汰顺序。所以要先搞清楚题目到底要什么。

3. 整除的尾数：枚举不是笨办法，但规律更快

3.1 题面与第一反应

“整除的尾数”这题一般这样描述：给定一个整数m，在它末尾补上n位数字，补完之后的新数要能被k整除，输出所有可能的n位尾数串。

比如m=123、n=2、k=12，就是要找所有两位尾数y，让12300 + y能被12整除。这里能整除的尾数不只是一个，而是一串。

我第一次做这题时第一反应就是暴力拼接：直接枚举0到10^n-1的所有尾数，拼到m后面试除一遍。n较小的时候完全可行，代码也短。很多人觉得暴力枚举丢人，其实在竞赛里，能过题才是硬道理。优化是后话。

这题最核心的数学表达是：

m × 10^n + y ≡ 0 (mod k)

只要把这个式子拆开看，后面所有的优化都有依据。

3.2 暴力拼接与取模判定

先写最直接的版本。关键点是用base表示10^n，然后遍历y。但这里有个新手常踩的坑：直接用m * base + y做取模，如果m和base都比较大会溢出int。所以最好拆开取模：

int r = (m % k) * (base % k) % k; if ((r + y) % k == 0) { ... }

为什么这样拆？因为取模运算对乘法和加法都能保留余数一致性：

(m × base + y) % k == ((m % k) × (base % k) % k + y) % k

这样即使m、base都很大，中间结果也永远小于k的平方，不会爆int。这是一个非常通用的技巧，后面做大数整除判定都能用。

3.3 用余数直接定位，从枚举改成步进

如果只想知道“有哪些尾数”，不需要每个y都去取模一次。我们可以先算出需要的余数：

int need = (k - (m % k) * (base % k) % k) % k;

只要y满足y % k == need，整体就能被k整除。于是第一个答案就是y = need，后面的答案每次加k即可：

for (y = need; y < 10^n; y += k) { 输出 y; }

这样做把枚举量从10^n降到了大约10^n/k，而且省掉了大量取模运算。如果要求输出全部结果，这已经接近理论最优了，因为答案个数本身差不多就是那么多。

为了处理n比较大时10^n溢出，完整代码里我用long long存放枚举上限，并且用base % k的递推来计算10^n对k的余数。

3.4 输出格式里最容易丢分的点

这个题的测评通常对输出格式非常严格，我总结出三个高频丢分点。

一是空格。多个结果用空格分隔，最后一个结果后面不能有空格。最简单的方式是用一个used标志位，第二个输出开始前先打一个空格。

二是前导零。题目要求“n位尾数”，那么y=0时要输出00（n=2时），不能输出0。C语言的printf("%0*d", n, y)可以按宽度补零，这条很好使。

三是无解情况。不是所有数据都有解。有的题要求什么都不输出，有的要求输出No这类标志，一定要先读清题。我习惯在程序里设置一个has标志，最后统一判断。

另外如果m可能是负数，记得先把m修正成正余数：m = (m % k + k) % k，不然取模结果可能是负数，need就算错。

3.5 整除尾数的完整代码

#include <stdio.h> void tailDiv(int m, int n, int k) { long long base = 1; for (int i = 0; i < n; i++) base = base * 10 % k; int r = (m % k + k) % k; int need = (k - r * base % k) % k; long long limit = 1; for (int i = 0; i < n; i++) limit *= 10; int used = 0; int has = 0; for (long long y = need; y < limit; y += k) { if (used) printf(" "); printf("%0*d", n, (int)y); used = 1; has = 1; } if (!has) printf("no solution"); printf("\n"); } int main() { tailDiv(123, 2, 12); // 期望：00 12 24 36 48 60 72 84 96 tailDiv(5, 1, 3); // 期望：1 4 7 return 0; }

跑一下，输出分别是：

00 12 24 36 48 60 72 84 96 1 4 7

第一组数据里00那个前导零必须输出，不然直接判错。

4. 回文质数：剪枝顺序决定运行时间

4.1 题面与两种判定的先后

题目通常是：给定区间[L, R]，输出区间内所有“既是回文数又是质数”的数。

判断一个数是否满足条件，要执行两个子判断：回文判断、质数判断。顺序很关键。我建议先判回文，再判质数。

原因很简单，回文数在自然数里占比低得多。比如1到10000里只有不到200个回文数，而素数有好几千个。如果先判质数，你会在大量根本不是回文的数字上白白做质数判定；如果先判回文，大部分数字直接就被筛掉了，质数判定的次数大幅减少。

对于三位数范围，这个顺序差别不大。但如果区间上限到10^7以上，差别是数量级的。

4.2 质数判定怎么写才可靠

质数判定的标准写法是试除法，到sqrt(n)为止：

int isPrime(int x) { if (x < 2) return 0; if (x == 2) return 1; if (x % 2 == 0) return 0; for (int i = 3; i <= x / i; i += 2) { if (x % i == 0) return 0; } return 1; }

这里有两个细节很多人不注意。

第一，i <= x / i比i * i <= x更安全。当x很大时，i * i可能溢出int，变成负数，循环条件直接错乱。用除法就没有这个问题。

第二，先排除偶数，然后i从3开始每次加2，直接把试除量减半。虽然常数级优化，但代码也没变复杂，没理由不写。

如果区间很大，比如一次查100万个数，每个数都从3试除到sqrt(n)，整体会很慢。这时建议先做一次埃氏筛，把区间内所有质数标记好，后续判断变成查表：

int isPrimeSieve[10000005]; void buildSieve(int limit) { for (int i = 2; i * i <= limit; i++) { if (!isPrimeSieve[i]) { for (int j = i * i; j <= limit; j += i) { isPrimeSieve[j] = 1; } } } }

标记数组里0代表质数，1代表合数。这样主循环里直接if (!isPrimeSieve[x])就能判断，不需要反复跑试除。

4.3 回文数判定的两种写法

回文数判定最直观的写法是转字符串比头尾。但C语言里转字符串要折腾字符数组，理论上没问题，实际上写起来容易犯低级错误。

我更喜欢用整数反转法：

int isPal(int x) { int tmp = x; int rev = 0; while (tmp) { rev = rev * 10 + tmp % 10; tmp /= 10; } return rev == x; }

原理很简单：把数字从低位到高位反向拼接，如果拼出来的数和原数相等，说明正反读一样，就是回文。比如x=12321，反转后还是12321，返回真。x=123，反转成321，返回假。

这个方法唯一要注意的是，反转过程中rev可能溢出int。好在正常题目范围里回文数判定不会用到极端大的数，如果你确实要处理很大的数，可以用long long，或者改成字符数组比较。

4.4 特殊剪枝：偶数位数回文数，质数只有11一个

回文质数这题最漂亮的地方在这里：除了11以外，所有偶数位的回文数都能被11整除，所以它们都不可能是质数。

为什么？看四位数回文abba，它等于1001×a + 110×b，而1001 = 11×91，110 = 11×10，所以它一定是11的倍数。六位数、八位数也一样，利用被11整除的判定规则：奇数位数字和与偶数位数字和相等，差为0，因此能被11整除。

这意味着如果区间上限超过100，你根本不需要检查那些偶数位的回文数。唯一要特别处理的偶位数回文质数就是11本身。

所以优化思路就清晰了：先单独输出11，然后只生成奇数位的回文数，再对它们做质数判定。生成奇数位回文数可以用“前半部分”来构造：

int buildOddPal(int half) { int p = half; int t = half / 10; while (t) { p = p * 10 + t % 10; t /= 10; } return p; }

比如half=12，构造出来是121；half=123，构造出来是12321。这个构造方法比暴力枚举+反向拼接要快得多，因为你根本不会生成那些偶数位的回文数。

4.5 回文质数完整实现与测试

先给一个暴力但直接的正确版本，适合区间不大的情况：

#include <stdio.h> int isPrime(int x) { if (x < 2) return 0; if (x == 2) return 1; if (x % 2 == 0) return 0; for (int i = 3; i <= x / i; i += 2) if (x % i == 0) return 0; return 1; } int isPal(int x) { int tmp = x, rev = 0; while (tmp) { rev = rev * 10 + tmp % 10; tmp /= 10; } return rev == x; } int main() { int L = 1, R = 1000; for (int i = L; i <= R; i++) { if (isPal(i) && isPrime(i)) printf("%d ", i); } printf("\n"); return 0; }

输出：

2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929

注意1不是质数，否则会混进答案。

如果区间很大，比如L=100，R=10^9，暴力遍历就不划算了。这时用奇数位回文生成法：

#include <stdio.h> int isPrime(int x) { /* 同上 */ } int buildOddPal(int half) { int p = half; int t = half / 10; while (t) { p = p * 10 + t % 10; t /= 10; } return p; } int main() { int L = 100, R = 1000000; if (L <= 11 && R >= 11) printf("11 "); for (int half = 1; ; half++) { int p = buildOddPal(half); if (p > R) break; if (p >= L && isPrime(p)) printf("%d ", p); } printf("\n"); return 0; }

这个版本生成的全是奇数位回文数，配合11单独处理，既不会漏，也避开了所有偶数位无用的判定。

5. 三个程序合体：从单题调试到综合测试

5.1 统一封装思路

刷题到一定阶段，我习惯把每个题目写成一个独立函数，在main里只负责调用和打印。这样有三个好处。

第一，便于针对多组数据测试。机试题通常要跑好几个样例，一个函数接参数直接循环调用就行。第二，思路清晰。写函数时先想输入、输出和返回条件，这本身就是在理清算法。第三，方便复用。比如isPrime这个函数后面做数论题还会反复用到，封装好之后直接复制到新工程里。

约瑟夫环封装成void josephusCircle(int n, int a, int b)，整除尾数封装成void tailDiv(int m, int n, int k)，回文质数封装成void palPrime(int L, int R)，三个函数各干各的事，main里依次调用，逻辑非常清爽。

5.2 测试用例设计与现场结果

这组题我最常用的一组测试数据，给你直接抄去验证自己的代码：

有一个边界必须单独测：双线约瑟夫环n=1。只有一个人时，无论走几步都应该直接淘汰这个人。我的完整代码能正常处理，因为while循环第一轮就会把编号1淘汰。但如果你写的时候用了while (outCnt < n - 1)，n=1时连循环都进不去，最后找你最长下标会发现根本没有未淘汰者，容易数组越界。建议对n=1做一次特判，或者像我这样用“淘汰到只剩0人”的循环逻辑。

5.3 复杂度对比总结

写完之后对比一下三种做法的复杂度，也方便以后根据数据范围选方案：

这套对比做完，遇到类似题时可以很快判断：数据规模允许暴力吗？必须上优化吗？哪种优化能保留全部答案？方向对了，后面就是套模板的事。

6. 刷题避坑指南与长期心得

6.1 day8最常见的三个坑

这三道题虽然内容不同，但我发现新手栽跟头的地方高度集中，几乎都逃不出下面三件事。

第一，环形下标反向越界。逆时针移动时忘了先加n再取模，直接访问负数下标，程序要么崩要么给出莫名其妙的结果。建议统一写成(cur + dir + n) % n。

第二，差一错误。约瑟夫环的起点到底在哪，循环次数到底用step还是step-1，整除尾数的枚举是从0开始还是从1开始，这类差一问题在每道题都会出现一次。解决办法只有一个：手动模拟一组小数据，把过程写在纸上，确认自己的程序逻辑和手算结果一致再往下走，不要对着屏幕瞎猜。

第三，输出格式不规范。空格多了、最后多换行、前导零没输出、无解时没处理好，这些不考察算法却考察细心。我在这里丢过的分比算法错误丢的分还多，后来养成的习惯是：先看输出样例，再写代码，最后专门写一个检查输出空格和空行的环节。

6.2 数组标记法的边界经验

约瑟夫环的数组标记法看起来简单，真正写起来有几个细节很磨人。

标记数组初始化为0，代表所有人都没出圈。每次淘汰一个人就置1。找下一个人的时候，一定要跳过所有标记为1的位置，这个跳过过程我建议用while而不是if，因为可能连续多个位置都已经出圈了。

出圈后重新定位起点时，要沿“当前方向”找下一个在场者，而不是随便找个位置。如果方向已经切换了再找起点，起点就会落在错误的一侧，后续整轮全部偏移。我在写双向代码时，有一段是先找起点再切换方向，结果找起点用的还是旧方向，排查了十分钟才看出问题。

还有一个经验：在调试循环类题目时，在关键位置加临时打印，比如输出每一轮的起点、方向、步数、淘汰编号。很多问题一眼就能看出来。调试完再删掉打印。

6.3 数学规律必须配合边界验证

这一天的三道题里，有两道依赖数学规律：整除尾数用余数定位，回文质数用11整除特性。数学规律很优美，但边界条件一定要单独验证。

回文质数里，11本身是质数，它同时也是偶数位回文数，所以生成奇数位回文时你得单独把它加上。还有1，它既不是质数也不是合数，回文判断会返回真但质数判断必须过滤掉。如果区间从1开始，不对1单独处理就会把1混进结果。

整除尾数里，need可能为0，此时第一个答案是0而不是k或k的倍数。输出时还要注意前导零。如果m本身是负数，直接取模会得到负数余数，必须先用(m % k + k) % k修正，否则所有结果全错。

我个人操作中的体会是：第8天这三道题，最值得回味的不是“会不会做”，而是“能不能一遍做对”。算法思路花点时间总能想出来，真正拉开差距的是边界意识和细节处理。如果你现在也卡在这一天的题，别急着往后刷，把这三个坑一个个改掉，后面的大量循环题会顺很多。这三题我建议每个人都亲手敲一遍，不要只看思路，因为下标和余数的感觉，只有在键盘上才能形成肌肉记忆。