note[0]

某个学MO的朋友给我看的题

这题似乎是1994年国家数学集训队选拔考试D1T1

怪不得我做了好久（

upd.20220513 害，他半途而废退役了

---

题面：

求四个所有的由四个自然数 \(a,b,c,d\) 组成的数组，使数组中任意三个数的乘积除以剩下的一个数余数为 \(1\)

题解：

（注：我写的可能有点不太正式，毕竟我只是个OIer）

由题意可得

\(abc \equiv 1 \mod d\)

\(abd \equiv 1 \mod c\)

\(acd \equiv 1 \mod b\)

\(bcd \equiv 1 \mod a\)

可化为

\(d\mid (abc-1)\)

\(c\mid (abd-1)\)

\(b\mid (acd-1)\)

\(a\mid (bcd-1)\)

\(\therefore ab\mid (acd-1)(bcd-1) \Rightarrow ab\mid (abc^2d^2-acd-bcd+1)\)

\(\therefore ab\mid (acd+bcd-1)\)

同理 \(cd\mid (abc+abd-1)\)

\(\therefore abcd\mid (a^2bc^2d+ab^2c^2d+a^2bc^2d+ab^2cd^2-abc-abd-acd-bcd+1)\)

\(\therefore abcd\mid (abc+abd+acd+bcd-1)\)

设 \(t=\dfrac{abc+abd+acd+bcd-1}{abcd}\)

\(\therefore t=\dfrac{1}{a}+\dfrac{1}{b}+\dfrac{1}{c}+\dfrac{1}{d}-\dfrac{1}{abcd}\)

显然 \(a,b,c,d\) 两两互质，且 \(a \ge 2\)

由于不考虑顺序，则假设 \(2\le a < b < c < d\)

\(\therefore t< \dfrac{4}{a} \le 2\)

\(\because t\in \mathbb{Z}^+\)

\(\therefore a=2,3,t=1\)

当 \(a=3\) 时，\(t_{max} = \dfrac{1}{3}+\dfrac{1}{4}+\dfrac{1}{5}+\dfrac{1}{6}-\dfrac{1}{360} = \dfrac{341}{360}<1\)\(\quad\therefore\)舍去

当 \(a=2\) 时，\(t_{max} = \dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{5}+\dfrac{1}{7}-\dfrac{1}{210} = \dfrac{246}{210}>1\)

\(\therefore a =2\)

\(\therefore \dfrac{1}{2}<\dfrac{3}{b}\)

\(\therefore b=3,5\)

当 \(b=5\) 时，\(t_{max} = \dfrac{1}{2}+\dfrac{1}{5}+\dfrac{1}{7}+\dfrac{1}{9}-\dfrac{1}{630} = \dfrac{600}{630}<1\)\(\quad\therefore\)舍去

当 \(b=3\) 时，\(t_{max} = \dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{5}+\dfrac{1}{7}-\dfrac{1}{210} = \dfrac{246}{210}>1\)

\(\therefore b=3\)

\(\therefore \dfrac{1}{6} < \dfrac{2}{c}\)

\(\therefore c=7,11\)

当 \(c=7\) 时，\(t_{max} = \dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{7}+\dfrac{1}{11}-\dfrac{1}{462} = \dfrac{492}{462}>1\)

当 \(c=11\) 时，\(t_{max} = \dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{11}+\dfrac{1}{13}-\dfrac{1}{858} = \dfrac{858}{858}=1\)

显然当 \(c=11\) 时 \(d=13\)

则一组解为 \(2,3,11,13\)

当 \(c=7\) 时

\(\dfrac{1}{42}<\dfrac{1}{d}\)

\(\therefore d=41\)

则另一组解为 \(2,3,7,41\)

综上所述，答案为 \(2,3,11,13\) 或 \(2,3,7,41\)

---

为了验算结果我直接敲了个 \(O(n^4)\) 的暴力（傻）