super ez problem series 2
luogu_gza
·
·
学习·文化课
我没有这些题的标准答案，如果你找到了我的做法中的错谬，请及时指点！
感谢反物质维度群群主和一些群友提供了这些有趣的题。
一
求所有正整数对 (a,b)，令 ab^2+b+7 整除 a^2b+a+b。
::::info[solution]
我们考察 ab^2+b+7|a^2b+a+b 可以推 ab^2+b+7|b(a^2b+a+b)-a(ab^2+b+7)=b^2-7a，进行分讨。
-
b^2-7a=0$，则令 $b=7k$，有 $a=7k^2
-
-
b^2-7a>0$ 这种情况不可能，因为有 $ab^2+b+7-(b^2-7a)=(a-1)b^2+7a+b+7>0
| 综上我们只有这几种解，(11,1),(49,1),(7k^2,7k)(k \in \N^*)。 |
二
好漂亮的题！
求所有质数对 (x,y) 满足 xy|5^x+5^y。
::::info[solution]
我们分类讨论：
-
x=y
令 x=y=p，有 p^2|2 \times 5^p，易得只有 p=5 满足。
-
x=5\lor y=5
不妨设 x=5,y \neq 5，则 5y|5^5+5^y，这等价于 y|5^5+5^y，由费马小定理这又等价于 y|5^5+5=2 \times 5 \times 313，这帮助我们寻到了四组解 (2,5),(313,5),(5,2),(5,313)。
-
(x=2 \lor y=2) \land (x \neq 5 \land y \neq 5)
不妨设 x=2,y\neq 2,5，有 2y|25+5^y，这等价于 y|25+5^y，同情况 2 可得两组解 (2,3),(3,2)。
-
x\neq 5 \land y \neq 5 \land x \equiv 1 \pmod 2 \land y \equiv 1 \pmod 2
综上，只有这七组解，$(5,5),(2,5),(313,5),(5,2),(5,313),(2,3),(3,2)$。
::::
### 三
给定一个正整数 $n$，要求构造 $n \times n$ 的正整数矩阵，满足每行、列、正反对角线都可以算 24 点，且行、列、正反对角线上的数所构成的可重集互不相同。
出题人：@yummy。
::::info[solution from yummy]
I have no words for this solution,anyone who can come up with it is an absolute genius.
::::
::::info[solution from gza]
首先判掉 $n$ 较小的情况，这可以爆搜我懒了。
第一行填 $24$，第一列除了 $(1,1)$ 填 $25$，最后一列除了 $(n,1)$ 填 $1$。
剩下的格子填 $i+2j+c$（其中 $c$ 是一个足够大的整数）。
接下来我们来证明这个构造是满足条件的。
行是 $25$，$d=1$ 的等差数列和 $1$，特殊地，第一行是一堆 $24$。
列是 $24$，$d=2$ 的等差数列，特殊地，最后一列是 $24$ 和一堆 $1$。
正对角线是 $24$，$d=3$ 的等差数列和 $1$，反对角线是 $24$，$d=1$ 的等差数列和 $25$。
$24$ 和一个等差数列 $a$ 可以用 $24+(a_1+a_4-a_2-a_3)\times a_5 \times a_6 \times \cdots=24$ 凑，每一行就考虑用 $25-1=24$，然后还是按照 $24$ 和一个等差数列 $a$ 的情况做。
::::
**提示：接下来两个题有一定的关联性。**
### $\frac{11}{3}
平面上有 10 个点，求证你一定能用若干个互相不交的单位圆来覆盖这 10 个点。
::::info[solution]
考虑你让圆尽量密铺平面，覆盖率是 \frac{\pi}{2\sqrt 3} \approx 0.9069，随机平移和旋转密铺方案，一个点被覆盖的概率就大约是 0.9069，因此随机平移和旋转密铺方案后 10 个点被覆盖个数期望是 9.069，最大值一定是整数且大于等于期望，因此一定存在一种覆盖 10 个点的方案。
::::
\frac{13}{3}
求证无向图的最大独立集一定 \geq \sum_{i=1}^{n}\frac{1}{1+d_i}，其中 d_i 是点 i 的度数。
::::info[solution]
考虑一个独立集的随机算法，随一个排列，一个点被选的条件是它的所有相邻点都在它之后，那么一个点被选中的概率是 \frac{1}{1+d_i}，自然的被选中点的个数期望是 \sum_{i=1}^{n}\frac{1}{1+d_i}，最大独立集也就 \geq \sum_{i=1}^{n}\frac{1}{1+d_i} 了。
::::
五
我深爱着数论啊。
正整数 n 至少有 6 个正因数，这些因数从小到大为 1=d_1<d_2<d_3<...<d_x=n，求所有满足 n=d_5^2+d_6^2 的正整数 n。
::::info[solution]
令 d_5=a,d_6=b，有 a|a^2+b^2,b|a^2+b^2 即 a|b^2,b|a^2，因此 a,b 质因子集合相同，且有 d_0(a) \leq 5,d_0(b) \leq 6，其中 d_0(n)=\sum_{d|n}1。
-
令 a=p^e，有 e \leq 4，令 b=p^f，有 f \leq 5 且 e<f \leq 2e。接下来逐一检查 (e,f) 对。
$e=2,f=3$：$n=p^4(p^2+1)$，而 $p^2<p^2+1<p^3$，$a,b$ 无法紧邻。
$e=2,f=4$：$n=p^4(p^4+1)=p^3(p^5+p)$，而 $p^2<p^3<p^4$，$a,b$ 无法紧邻。
$e=3,f=4$：$n=p^6+p^8=p(p^2+1)p^5$，而 $p^3<p(p^2+1)<p^4$，$a,b$ 无法紧邻。
$e=3,f=5$：$n=p^6+p^{10}=p^4(p^2+p^6)$，而 $p^3<p^4<p^5$，$a,b$ 无法紧邻。
$e=4,f=5$：$n=p^8+p^{10}$，而 $1,p^2,p^2+1,p^3,p^3+p|n$ 且 $a=p^4$，$1,p^2,p^2+1,p^3,p^3+p<p^4$，$a$ 不可能为第 $5$ 个因数。
2. $a$ 有两个不同的质因子
令 $a=pq$，不妨设 $p<q$，有 $b=pq^2 \lor b=p^2q$。
若 $b=pq^2$，则有 $pq<q^2<pq^2$，$a,b$ 无法紧邻，因此 $b=p^2q$，此时有 $n=p^2q^2(1+p^2)$。由 $d_0(b)=6$ 有 $d_1 \sim d_6$ 其实就是 $b$ 的所有因子，又因 $1+p^2|n,1+p^2<p^2q=b$ 推得 $1+p^2|b$，又 $\gcd(1+p^2,p)=1$ 所以存在 $k$ 使得 $1+p^2=q^k$。
若 $k \geq 2$ 则 $q^2 \leq q^k=1+p^2$，而 $q>p \rightarrow q^2>p^2+1$，矛盾，因此 $k=1$，此时有 $q=p^2+1$，$p,q$ 奇偶性不同，从而可以发现 $(p,q)$ 只有一种可能性，$p=2,q=5$，可以得到 $n=500$ 是唯一的解！
::::
::::info[simpler solution from @无名之雾]
::::