题解：P12831 [蓝桥杯 2025 国 B] 互质藏卡
Sunrise_up
·
·
题解
思路
我们发现这个 17600 似乎有些不合规律，我们惊奇的发现：这里刚好有 2024 个质数！
那我们要这个 2025 个数互质，肯定是这样的：
假设 p_i 为第 i 个质数，k_i 为符合的正整数，使得 p_i^{k_i}\le 17600，则这些数为：1,p_1^{k_1},p_2^{k_2},p_3^{k_3},\dots,p_{2024}^{k_{2024}}。
我们只需求出前 2024 个质数，并求出其最大的 k_i 即可。
答案即为：
k_1\times k_2\times k_3\times\dots\times k_{2024} \mod (10^9+7)
你可以使用编程，但是这里我就用数学解法了。
由于 17600 以内有 2024 个质数，其中小于等于 \sqrt{17600} \approx 132.66 的质数有 32 个，其余 1992 个质数的平方均大于 17600（故 k_i = 1）。
计算前 32 个质数的幂次上限：
$p=3:\ 3^8 = 6561 \leq 17600$，故 $k_2=8$。
$p=5:\ 5^6 = 15625 \leq 17600$，故 $k_3=6$。
$p=7:7^5 = 16807 \leq 17600$，故 $k_4=5$。
$p=11:\ 11^4 = 14641 \leq 17600$，故 $k_5=4$。
$p=13,17,19,23:\ 13^2,17^2,19^2,23^2\leq 17600$，故 $k_6=k_7=k_8=k_9=3$。
其余 $23$ 个 $\leq 132$ 的质数：$p_i^2\leq17600$， 但是 $p_i^3>17600$，其中 $i\in(10,32)$，故 $k_{10} \sim k_{32}=2$。
计算乘积并取模：前 $9$ 个质数的 $k$ 乘积为 $14 \times 8 \times 6 \times 5 \times 4 \times 3 \times 3 \times 3 \times 3 = 1088640$，后 $23$ 个质数的 $k$ 均为 $2$，故总乘积为 $1088640 \times 2^{23} \mod (10^9+7)$。
$$\begin{align*}
&1088640 \times 2^{23} \mod (10^9+7) \\
=&1088640 \times 8388608 \mod 1000000007 \\
=&9132174213120 \mod 1000000007 \\
=&174149196
\end{align*}$$
答案即为 $174149196$。
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<174149196;
return 0;
}
```
如果有用的话，请点个赞吧 qwq！