CPCTF - Modulo Equation Writeup¶

题目信息¶

比赛: CPCTF
题目: Modulo Equation
类别: PPC
难度: 简单
附件/URL: 无附件，标准输入输出题
附件链接: 无附件
Flag格式: CPCTF{...}
状态: 已解

Flag¶

CPCTF{D1d_y0u_8ru73_f0rc3_17!?}

解题过程¶

1. 初始侦察/文件识别¶

题目给定正整数 \(A, B\)，并保证 \(A > B\)。
目标是求满足下面条件的最小正整数 \(x\)：

\[ x \bmod A = B \bmod x \]

约束是：
\(1 \leq B < A \leq 300\)
一定存在满足条件的正整数 \(x\)
最小解不超过 \(10^5\)
题目提示其实已经把做法说得很直白了：既然保证答案存在，而且最小值不会超过 \(10^5\)，那就可以直接从 \(1\) 开始往上枚举。

2. 关键突破点一¶

这题最容易让人多想，例如尝试把同余条件拆成很多分类讨论。
但题目已经给了一个非常强的上界：

\[ \text{answer} \leq 100000 \]

这意味着就算最朴素地检查 \(x = 1, 2, 3, \ldots\)，总共也只需要做最多 \(10^5\) 次判断。
每次判断只涉及两次取模：

\[ x \bmod A \]

\[ B \bmod x \]

在当前约束下，这个复杂度非常轻，完全足够 AC。

3. 关键突破点二¶

因为题目要求的是最小值，顺序枚举还有一个天然好处：
一旦遇到第一个满足条件的 \(x\)
就可以立即输出并结束
不需要维护最优答案，也不需要做额外比较。
伪代码就是：

\[ \text{for } x = 1, 2, 3, \ldots:\quad \text{if } x \bmod A = B \bmod x,\ \text{print}(x)\ \text{and break} \]

4. 获取 Flag¶

直接按提示暴力枚举，Go 代码如下：

package main

import (
    "fmt"
)

func main() {
    var a, b int
    fmt.Scanln(&a, &b)
    for x := 1; ; x++ {
        if x%a == b%x {
            fmt.Println(x)
            break
        }
    }
}

提交通过测试点 AC 后，平台给出的 flag 为：

CPCTF{D1d_y0u_8ru73_f0rc3_17!?}

攻击链/解题流程总结¶

读取 \(A\) 和 \(B\) -> 从 \(x=1\) 开始顺序枚举 -> 检查 \(x \bmod A\) 是否等于 \(B \bmod x\) -> 第一个满足条件的 \(x\) 立即输出

漏洞分析 / 机制分析¶

根因¶

这是标准 PPC / 算法题，不涉及漏洞利用。
题目的关键不在数学变形，而在正确理解提示给出的“存在性 + 上界”信息。

影响¶

如果忽略题目给出的解存在且不超过 \(10^5\) 这个条件，容易把简单题做复杂。
只要利用这个信息，朴素枚举就是正确且足够快的解法。

修复建议（适用于漏洞类题目）¶

若这是实际工程逻辑，不应无上界地暴力枚举。
但在竞赛题里，如果已经明确给出解的存在性和上界，顺扫通常就是最稳的实现方式。

知识点¶

取模运算的直接模拟
利用题目给出的答案上界设计暴力解
“最小满足条件值”与顺序枚举的天然匹配

使用的工具¶

Go — 顺序枚举 x 并输出首个满足条件的答案
题面提示 — 明确告知答案存在且不超过 \(10^5\)

脚本归档¶

Go：CPCTF_Modulo_Equation.go
说明：脚本直接按题目提示从 1 开始枚举到首个满足条件的 x

命令行提取关键数据（无 GUI）¶

echo "10 4" | go run CTF_Writeups/scripts_go/CPCTF_Modulo_Equation.go

推荐工具与优化解题流程¶

题目已经明确告诉你“解存在且最小值不超过 \(10^5\)”，这就是最关键的提示。该暴力时就直接暴力。

工具对比总结¶

工具	适用阶段	本题耗时	优点	缺点
直接顺扫枚举	正解	秒级	最稳、最短、最不容易错	需要注意是“第一个解”
数学分类讨论	过度分析	不定	可能更优雅	对这题完全没必要
手动代值	验证样例	秒级	易于理解条件	不能替代程序提交

工具 A（推荐首选）¶

安装：Go
详细步骤：
读入 \(A, B\)
从 \(x = 1\) 开始循环
检查 \(x \bmod A = B \bmod x\)
第一次成立时输出 \(x\) 并结束
优势：与题目提示完全一致，最适合 AC 后归档

工具 B（可选）¶

安装：任意支持循环和取模的语言
详细步骤：也可以用 Python / C++ 实现同样的顺序枚举。
优势：逻辑完全相同，语言切换成本极低