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

· · 题解

思路分析

看到要求 a + b 必须是 2025 的倍数，这就说明了 a + b \mod 2025 = 0。

如果直接枚举 a,b，会多出来不必要的枚举次数，因为这些枚举次数都是 a + b 的和都不是 2025 的倍数，就不满足条件 3。

for(LL i = 2025; i <= (LL)(1e6); i += 2025)

对于条件 2，a 和 b 互素，即 a 和 b 的最大公约数为 1。这里可以使用 __gcd() 函数计算最大公因数，判断一下是不是 1 就好了，即 \gcd(a,b) = 1。

if(a < b && __gcd(a, b) == 1)

对于条件 1，这就是我们枚举的上限。

代码实现

这里提供一份 C++ 的暴力代码：

#include<bits/stdc++.h>
#define please return 
#define AC 0

using namespace std;

typedef long long LL;
LL ans = 0;
signed main() {
    for(LL i = 2025; i <= (LL)(2e6); i += 2025) {
        for(LL j = max(1LL, i - (LL)(1e6)); j <= min(i * 1LL, (LL)(1e6)); j++) {
            LL x = i - j;
            if(j < x && __gcd(j, x) == 1) ++ans;
        }
    }
    printf("%lld\n", ans);
    please AC; 
}

运行可得答案为 93816892。

使用 Python 输出答案：

print(93816892)