(log求因数和)北京建筑大学2024年程序设计竞赛 B因数之和

题意：

计算一个数的所有因数的和通常涉及质因数分解，然后对每个质因数的幂次进行求和运算。
具体步骤如下：
1.质因数分解：首先，将给定的数进行质因数分解，表示为\(2^{a}*3^{b}*5^{c}....\)
2.计算每个质因数的贡献：对于每个质因数p（如2, 3, 5等），计算从p^{0}到p的所有数的和
3.这可以通过等比数列求和公式完成，即$p^{a}+p*p^{a-2}+....+p+p^{0}=\frac{p-1}{p-1} $
4.乘积运算：将所有质因数的贡献相乘，即(2^{a}+2+2^{a-2}+...+2+2^{0})*(3+3^{b-1}+3+...+3^{1}+3)....

思路：
知道了求因数和的方法后，我们显然要对每个数进行一次分解质因数，但是一看数据范围1e6,而正常分解质因数复杂度是\(\sqrt{n}\)，显然超时。
我们考虑先用线性筛预处理出来所有的质数，这样复杂度会降低到log级别。再用因数求和公式计算和，然后统计答案即可。

code：

#include <bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using PII = pair<i64, i64>;
const int inf = 0x3f3f3f3f;
const i64 INF = 0x3f3f3f3f3f3f3f3f;
#define Z cout << "\n"
#define lb lower_bound
#define ub upper_bound
#define D(x) cerr << #x << ": " << (x) << "\n"
#define DV(v) cerr<<#v<<": ";for(int i=0;i<(v).size();i++)cerr<<((v)[i])<<",";cerr<<"\n"
#if 0
#define int i64
#endif
const int N = 1e6 + 5;
int p[N], pr[N], tot;
void prim(int n) {
    for (int i = 2; i <= n; i++) {
        if (!p[i])p[i] = i, pr[++tot] = i;
        for (int j = 1; j <= tot && pr[j] * i <= n; j++) {
            p[i * pr[j]] = pr[j];
            if (i % pr[j] == 0) {
                break;
            }
        }
    }
}
map<int, int>mp;
void divide(int x) {
    while (p[x] > 1)mp[p[x]]++, x /= p[x];
    if (x > 1)mp[x]++;
}
const int P = 1e9 + 7;
i64 quick(i64 a, i64 n) {
    int res = 1;
    while (n) {
        if (n & 1) res = res * a % P;
        a = a * a % P;
        n >>= 1;
    }
    return res;
}
int inv(int x) {
    return quick(x, P - 2);
}
int s[N];
signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    prim(1e6 + 1);
    for (int i = 1; i <= 1e6; i++) {
        divide(i);
        i64 z = 1;
        for (auto [p, n] : mp) {
            z *= (quick(p, n + 1) - 1) * inv(p - 1) % P;
        }
        if (z >= 2 * i)s[i] = 1;
        mp.clear();
    }
    for (int i = 1; i <= 1e6; i++)s[i] += s[i - 1];
    int m;
    cin >> m;
    while (m--) {
        int x, y;
        cin >> x >> y;
        cout << s[y] - s[x - 1] << "\n";
    }
    return 0;
}