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)$ 的暴力（傻）