给你一副牌[1,2,3,4,4,3,2,1]，问能否按X ≥ 2张一组分组，且每组内数字相同。
第一反应可能是搜索、回溯、枚举 X。但正解只有：
gcd(所有数字的计数)>=2为什么？因为“能分组”这件事，本质上是在问“这些计数有没有大于1的公共因子”。
这就是数学类题目的典型形态：代码只有两三行，难点全在“看出它是 gcd”。
今天的三道题都是这样——LC.914、LC.365、LC.1071，每一道的解法代码都不超过十行，但如果没认出背后的模型，你可能会写出BFS（水壶问题的经典错解）或者一大段字符串处理。
本周的立意正在于此：先用数学消灭问题，再写代码。
📦 题目速览（30秒读懂）
题目1：卡牌分组（LC.914）
给定一副牌，选
X ≥ 2，使所有牌能分成若干组，每组 X 张且数字相同。示例：
[1,2,3,4,4,3,2,1]→true（X=2）；[1,1,1,2,2,2,3,3]→false
题目2：水壶问题（LC.365）
两个容量为
x、y升的水壶，无限水。能否得到恰好z升？示例：
x=3, y=5, z=4→true；x=2, y=6, z=5→false
题目3：字符串的最大公因子（LC.1071）
返回最长的同时能除尽
str1和str2的字符串。示例：
"ABCABC"+"ABC"→"ABC"；"LEET"+"CODE"→""
🧠 核心思路
欧几里得算法（辗转相除）
gcd(a, b) = gcd(b, a mod b) 直到b == 0，此时a即为最大公约数一行证明：设d是a和b的任意公约数，则d | a且d | b，于是d | (a - ⌊a/b⌋·b) = a mod b。反之若d | b且d | (a mod b)，则d | a。
两边的公约数集合完全相同，所以最大公约数也相同。
复杂度为什么是 O(log)？
每两步余数至少减半（若a mod b > b/2，则下一步b mod (a mod b) < b/2），所以余数序列按指数衰减。
最坏输入是相邻的斐波那契数——这正是“每步减得最慢”的情形。
defgcd(a,b):whileb:a,b=b,a%breturnaLC.914：建模成“公共因子”
设数字v出现了cᵥ次。要按X张一组分组，就必须让每种数字的计数都能被X整除——否则某一组里会混入不同数字。
于是问题变成：
存在
X ≥ 2使得X | c₁且X | c₂且 … ⟺gcd(c₁, c₂, ...) ≥ 2
注意是所有计数的总gcd，不是成对gcd。好消息是gcd满足结合律，用reduce累积即可，且gcd(0, x) = x让初始值0可以安全使用。
LC.365：建模成裴蜀定理
这是三题里最需要洞察力的一道。每次操作（装满、倒空、互倒）之后，两个水壶里的水量变化都可以表示为x和y的整数线性组合。所以：
能得到
z升 ⟺ 存在整数a, b使得a·x + b·y = z
而裴蜀定理给出：方程a·x + b·y = z有整数解，当且仅当gcd(x, y)整除z。
再加上物理约束z ≤ x + y，两者合起来才是充要条件：
z == 0 → true（什么都不做） z > x + y → false（装不下） z % gcd(x, y) == 0 → true⚠️只写gcd条件而漏掉z ≤ x + y是本题第一大错误——很多人只证了必要性就收手。
裴蜀定理的直观解释：所有能凑出的水量，恰好是gcd(x,y)的所有倍数。以x=3, y=5为例，gcd = 1，理论上能凑出任意整数升——比如4升：
装满5 → 倒进3（5剩2）→ 倒空3 → 把2倒进3 → 装满5 → 倒满3（需1，5剩4）得到4升 ✓。对应的裴蜀等式是4 = 5×2 + 3×(-2)，即a = 2, b = -2——系数允许为负，物理上对应“倒掉水”。
LC.1071：拼接判定
两个字符串存在公因子串，当且仅当str1 + str2 == str2 + str1。
这个结论需要证明，不能凭感觉：
- 必要性：若
str1 = T 重复m次、str2 = T重复n次，则str1 + str2与str2 + str1都是T重复m+n次，必然相等。 - 充分性：若
str1 + str2 == str2 + str1，则两个字符串循环同构，可以证明它们都由同一个长度为gcd(len1, len2)的前缀重复构成。
判定成立后，答案长度就是gcd(len1, len2)，直接取前缀即可。
⚠️必须先做拼接校验。直接返回str1[:gcd(len1,len2)]是错的——反例：str1 = "ABCABD"、str2 = "ABC"，长度gcd是3，但拼接不等，答案应是""而非"ABC"。
🖼️ 图解算法（手把手走一遍）
LC.365 的实际操作步骤（x=3, y=5，目标4升）
| 步骤 | 操作 | 3升壶 | 5升壶 | 说明 |
|---|---|---|---|---|
| 0 | 初始 | 0 | 0 | 两壶皆空 |
| 1 | 装满5升壶 | 0 | 5 | |
| 2 | 5 → 3（倒满） | 3 | 2 | 5升壶剩2 |
| 3 | 倒空3升壶 | 0 | 2 | |
| 4 | 5 → 3（倒2进去） | 2 | 0 | |
| 5 | 装满5升壶 | 2 | 5 | |
| 6 | 5 → 3（倒满，需1升） | 3 | 4 | 得到4升✓ |
把它翻译成裴蜀等式：4 = 5 + 5 - 3 - 3 = 2×5 + (-2)×3，即a = 2, b = -2✓。而gcd(3,5) = 1，1 | 4成立，且4 ≤ 3+5 = 8，两个条件都满足。
反例核对：x=2, y=6, z=5。gcd(2,6) = 2，而2 ∤ 5，所以false ✓——无论怎么倒，能凑出的水量只能是0, 2, 4, 6, 8（2的倍数），永远得不到5。
LC.914 的三组数据
| deck | 各数字计数 | 总gcd | ≥ 2？ | 答案 |
|---|---|---|---|---|
[1,2,3,4,4,3,2,1] | 1→2, 2→2, 3→2, 4→2 | 2 | ✅ | true |
[1,1,1,2,2,2,3,3] | 1→3, 2→3, 3→2 | 1 | ❌ | false |
[1,1,2,2,2,2] | 1→2, 2→4 | 2 | ✅ | true |
第二组为什么不行？计数的gcd是1，意味着找不到任何X ≥ 2能同时整除3、3、2。
LC.1071 的拼接判定
| str1 | str2 | str1+str2 | str2+str1 | 相等？ | 答案 |
|---|---|---|---|---|---|
"ABCABC" | "ABC" | "ABCABCABC" | "ABCABCABC" | ✅ | "ABC"（长度gcd=3） |
"ABABAB" | "ABAB" | "ABABABABAB" | "ABABABABAB" | ✅ | "AB"（长度gcd=2） |
"LEET" | "CODE" | "LEETCODE" | "CODELEET" | ❌ | "" |
💻 代码实现（Python + Java）
Python版
classSolution:# ---------- gcd（欧几里得）----------def_gcd(self,a:int,b:int)->int:whileb:a,b=b,a%b# 每两步余数至少减半 → O(log min(a,b))returna# ---------- LC.914 卡牌分组 ----------defhasGroupsSizeX(self,deck:list[int])->bool:fromcollectionsimportCounteriflen(deck)<2:returnFalseg=0forcntinCounter(deck).values():g=self._gcd(g,cnt)# 累积所有计数的总gcd（不是成对）returng>=2# ---------- LC.365 水壶问题 ----------defcanMeasureWater(self,x:int,y:int,z:int)->bool:ifz==0:returnTrueifz>x+y:# 容量约束：单靠gcd条件会漏判returnFalsereturnz%self._gcd(x,y)==0# 裴蜀定理# ---------- LC.1071 字符串的最大公因子 ----------defgcdOfStrings(self,str1:str,str2:str)->str:# 拼接校验不能省：长度gcd成立不代表真的存在公因子串ifstr1+str2!=str2+str1:return""returnstr1[:self._gcd(len(str1),len(str2))]Java版
classSolution{privateintgcd(inta,intb){while(b!=0){intt=a%b;a=b;b=t;}returna;}publicbooleanhasGroupsSizeX(int[]deck){if(deck.length<2)returnfalse;int[]cnt=newint[10000];for(intv:deck)cnt[v]++;intg=0;for(intc:cnt){if(c>0)g=gcd(g,c);// gcd(0, x) = x，天然正确}returng>=2;}publicbooleancanMeasureWater(intx,inty,intz){if(z==0)returntrue;if(z>x+y)returnfalse;// 漏掉这行会误判returnz%gcd(x,y)==0;}publicStringgcdOfStrings(Stringstr1,Stringstr2){if(!(str1+str2).equals(str2+str1)){return"";}returnstr1.substring(0,gcd(str1.length(),str2.length()));}}⚠️防坑提醒（必看）：
- LC.365 漏掉
z > x + y：裴蜀定理只保证“存在整数解”，但物理上两壶总容量只有x + y。例如x=1, y=1, z=3，gcd=1整除3，但装不下，必须返回false。- LC.914 用成对gcd：必须对所有计数做累积gcd（
g = gcd(g, cnt)）。- LC.1071 不做拼接校验：反例
"ABCABD"/"ABC"，长度gcd是3，但拼接不等，答案是""。
⏱️ 复杂度分析（面试必问）
| 题目 | 时间 | 空间 | 说明 |
|---|---|---|---|
| gcd | O(log min(a,b)) | O(1) | 每两步余数至少减半 |
| LC.914 | O(n + k logC) | O(k) | n 计数、k 种数字、C最大计数 |
| LC.365 | O(log min(x,y)) | O(1) | 只需一次 gcd |
| LC.1071 | O(n + m) | O(n + m) | 字符串拼接与比较 |
对比一下“不建模”的代价
| 题目 | 建模后 | 不建模的做法 | 差距 |
|---|---|---|---|
| LC.914 | O(n) | 枚举X从2到 n → O(n²) | 从平方降到线性 |
| LC.365 | O(log) | BFS搜索所有状态→ 状态数 O(x·y) | 从指数级降到对数级 |
| LC.1071 | O(n+m) | 枚举所有可能的因子串长度 → O(n²) | 从平方降到线性 |
LC.365 是最极端的例子：网上大量题解用BFS（把所有(水量1, 水量2)当作状态做搜索），代码几十行、状态数O(x·y)；而裴蜀定理的解法只需两行判断。认出模型，比写出搜索重要得多。
🚀 举一反三：6道高频变体题
| 题号 | 题目 | 与本题的关系 |
|---|---|---|
| LC.914 | 卡牌分组 | 计数gcd |
| LC.365 | 水壶问题 | 裴蜀定理（最经典的建模题） |
| LC.1071 | 字符串的最大公因子 | 拼接判定 + 长度gcd |
| LC.858 | 镜面反射 | gcd/lcm建模 |
| LC.1979 | 找出数组的最大公约数 | gcd的直接应用 |
| LC.1001 | 网格照明 | lcm建模 |
💬 面试追问模拟（提前准备，惊艳全场）
Q1：欧几里得为什么是O(log)？
每两步余数至少减半：设
r₁ = a mod b。若r₁ ≤ b/2，一步就减半；
若r₁ > b/2，则下一步b mod r₁ = b - r₁ < b/2。
所以余数每两步至少减半，步数O(log min(a,b))。最坏输入是相邻斐波那契数——每步商都是1，减得最慢。
Q2：裴蜀定理的“整数解”允许负数，物理上是什么意思？
对应“倒掉水”。LC.365里
4 = 2×5 + (-2)×3，b = -2就是“倒掉了2个3升壶的水”。
倒空操作让负系数变得可行。如果只允许“加水不允许倒水”，模型就不成立了。
Q3：lcm(a,b) = a / gcd(a,b) * b为什么要先除后乘？
防溢出。
a * b可能远超int范围，而a / gcd * b的中间结果最大是lcm本身。顺序不能颠倒。
Q4：模逆元怎么求？
若
a × x ≡ 1 (mod m)，则x是a的逆元，等价于求a·x + m·y = 1的整数解——正是裴蜀定理，且要求gcd(a, m) = 1（否则无解）。
两条路：
① 模为质数时用费马小定理a^(m-2)（快速幂）；
② 通用做法用扩展欧几里得算法——在辗转相除的同时回代求出系数x, y。
🧩 实战小技巧（刷题党必备）
- 口诀：辗转相除求gcd，裴蜀定理判可解；
z ≤ x+y不能漏，拼接校验不能省。 - 模板：
gcd(a,b)三行；z % gcd(x,y) == 0判裴蜀；str1+str2 == str2+str1判字符串。 - 防坑：LC.365漏容量判断会误判；LC.914用成对gcd会错；LC.1071不做拼接校验会错。
📈 实际应用场景（不止是刷题）
- 分数运算：约分就是分子分母同除 gcd
- 周期性对齐：两个周期分别为
a、b的任务，重合周期是lcm(a,b) - RSA与模运算：扩展欧几里得求私钥、求模逆元
- 图像缩放 / 网格对齐：
lcm与gcd决定最小可平铺单元
🎁 今日思考题（评论区见）
LC.365水壶问题，网上大量题解用 BFS。你觉得面试时应该直接写裴蜀定理（两行），还是先说BFS思路再升级到数学解？
提示：先展示“我能做出来”，再展示“我能做得更好”，通常是更稳的表达顺序。欢迎评论区聊聊你的看法 🧠
