2023 年山东预赛

思路

若gcd(u,v)=1且v整除g u²，则v整除g；两个互素数都整除g时，它们乘积整除g。奇数乘积不影响一个数可被二的几次幂整除。

想法从哪来：所取数的个数比某个二的幂所对应的奇剩余类数多一，先据此抽出同余的一对。它们的差含有很高的二次幂，原数却都是奇数，这种奇偶冲突需要把双向平方整除进一步拆开才能使用。若每一对都不满足结论，就两边互相整除对方的平方；约去最大公因数，剩余两个互素因子都必须整除公共部分。将公共部分再提取它们的乘积后，差的二因子只能落在两互素奇因子的差上，迫使较大者已经很大。它在原大数中至少出现平方，于是突破原区间上界。这里反证必须同时使用两个整除方向，不能只否定其中一边。

模 $2^{2n}$ 的奇数剩余类恰有 $2^{2n-1}$ 个，先用抽屉原理找到同余的两数。若它们彼此都整除对方的平方，约去最大公因数后会迫使一个过大的奇数因子出现，与区间上界矛盾。