求满足gcd(i,j)=C的数对个数的超时代码优化方案求助

问题转化 #

原问题要求计算满足 (N \geq i \geq j \geq 1) 且 (\gcd(i,j)=C) 的数对数量。我们可以通过变量替换简化问题：

• 令 (i = C \cdot x)，(j = C \cdot y)，则条件转化为 (x \leq \lfloor \frac{N}{C} \rfloor = M)，(y \leq x)，且 (\gcd(x,y)=1)。
• 此时问题等价于求 1到M中，所有x对应的欧拉函数值之和，即 (S(M) = \sum_{x=1}^M \varphi(x))，其中 (\varphi(x)) 是欧拉函数，表示1到x中与x互质的数的个数。

优化思路：杜教筛（杜氏筛） #

由于 (M) 可达到 (10^9)，普通欧拉筛无法处理，因此使用杜教筛高效计算欧拉函数的前缀和。核心原理基于数论卷积的性质：

1. 已知 (\sum_{d|n} \varphi(d) = n)，对两边求前缀和可得：
   [
   \sum_{i=1}^n \sum_{d|i} \varphi(d) = \sum_{i=1}^n i = \frac{n(n+1)}{2}
   ]
2. 交换求和顺序后变形为：
   [
   S(n) = \frac{n(n+1)}{2} - \sum_{d=2}^n S\left( \lfloor \frac{n}{d} \rfloor \right)
   ]
3. 结合记忆化搜索和分块加速（利用 (\lfloor \frac{n}{d} \rfloor) 的取值只有 (O(2\sqrt{n})) 种），同时预处理小范围（如 (10^6)）的欧拉函数前缀和，可将时间复杂度降至 (O(n^{2/3}))。

优化后的代码 #

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

const int MOD = 100000007;
const int PRE_SIZE = 1e6 + 5; // 预处理的欧拉函数范围
vector<long long> phi(PRE_SIZE);
vector<long long> pre_sum(PRE_SIZE);
unordered_map<long long, long long> memo;

// 预处理欧拉函数和前缀和
void init() {
    for (int i = 1; i < PRE_SIZE; ++i) phi[i] = i;
    for (int i = 2; i < PRE_SIZE; ++i) {
        if (phi[i] == i) { // i是质数
            for (int j = i; j < PRE_SIZE; j += i) {
                phi[j] -= phi[j] / i;
            }
        }
    }
    pre_sum[0] = 0;
    for (int i = 1; i < PRE_SIZE; ++i) {
        pre_sum[i] = (pre_sum[i-1] + phi[i]) % MOD;
    }
}

// 2的逆元，模100000007下等价于除以2
const long long inv2 = 50000004;

// 杜教筛计算S(n) = sum_{x=1}^n phi(x) mod MOD
long long du_sieve(long long n) {
    if (n < PRE_SIZE) return pre_sum[n];
    if (memo.count(n)) return memo[n];
    long long res = (n % MOD) * ((n + 1) % MOD) % MOD;
    res = res * inv2 % MOD; // 计算n*(n+1)/2 mod MOD
    long long l = 2, r;
    while (l <= n) {
        r = n / (n / l);
        long long cnt = (r - l + 1) % MOD;
        res = (res - cnt * du_sieve(n / l) % MOD + MOD) % MOD;
        l = r + 1;
    }
    memo[n] = res;
    return res;
}

void solve(int tt) {
    long long c, n;
    cin >> c >> n;
    long long M = n / c;
    cout << du_sieve(M) << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int tt;
    cin >> tt; // 支持多组测试用例，单组可移除
    while (tt--) {
        solve(tt);
    }
    return 0;
}

代码说明 #

• 预处理：先用欧拉筛计算1到 (10^6) 的欧拉函数值及其前缀和，小范围直接查询，减少递归次数。
• 杜教筛递归：对大于 (10^6) 的n，利用递推式计算，同时用哈希表存储已计算的结果避免重复计算。
• 分块加速：通过 (\lfloor \frac{n}{d} \rfloor) 的分块，将循环次数从O(n)降至O((\sqrt{n}))。
• 模运算处理：所有运算均对100000007取模，除法通过乘以逆元实现（因为MOD是质数，2的逆元为50000004）。

内容的提问来源于stack exchange，提问作者Owais Korejo