题解：P12869 [蓝桥杯 2025 国 Python A] 特殊整数对的数量

· · 题解

前言

作者通过了一些不太正规的方法 AC ，此题解仅作为思路参考！

题目传送门

思路

通过题目条件 1，我们知道 1≤a<b≤10^6。

通过题目条件 2，我们知道 __gcd(a,b)等于 1。

通过题目条件 3，我们知道 a+b 是 2025 的倍数。

通过以上三个条件，我们可以写出一个双层循环暴力，外层循环循环到 1e6-1，判断 b 的值是否 >a 的值，如果 b 的值 <a 的值，让 b 加 2025 ，内层循环循环到 1e6，每次 +2025，如果__gcd(a,b)等于 1，让计数器 +1。这里只放给 b 赋值的代码。

上述思路的时间复杂度是 O(n^2/2025)。

代码：

int b=a/2025*2025+(2025-a%2025);
if(b<a)b+=2025;

后记：

作者的方法：在 C++ 中直接硬暴力。