【NC17450】因数个数和

题目

因数个数和

因数个数，找规律

思路

根据题意，可以知道不可能使用朴素的方法挨个求解结果

对任意一个正整数 x x x，其所有因数的分布规律是要么小于等于 ⌊ x ⌋ \lfloor \sqrt x \rfloor ⌊x ​⌋，要么大于 ⌊ x ⌋ \lfloor \sqrt x \rfloor ⌊x ​⌋

于是可以枚举小于等于 ⌊ x ⌋ \lfloor \sqrt x \rfloor ⌊x ​⌋的因数，并在枚举过程中计算所有因数的个数之和。

对于小于等于 ⌊ x ⌋ \lfloor \sqrt x \rfloor ⌊x ​⌋的因数 i i i，可以直接求其贡献值，即 1 → x 1\to x 1→x 中有多少个数字含有该因子 i i i，可以求得 i i i 的贡献值为 ⌊ x i ⌋ \lfloor {x\over{i}} \rfloor ⌊ix​⌋，然后利用 i i i 求大于 ⌊ x ⌋ \lfloor \sqrt x \rfloor ⌊x ​⌋ 范围内的贡献，即找 i × m i\times m i×m，其中 m m m 是刚刚好大于 ⌊ x ⌋ \lfloor \sqrt x \rfloor ⌊x ​⌋ 并且 i × m i\times m i×m 还在 x x x 范围内的数字的个数，那么该数的范围为 ⌊ x ⌋ + 1 → ⌊ x i ⌋ \lfloor\sqrt x\rfloor+1 \to \lfloor {x\over{i}} \rfloor ⌊x ​⌋+1→⌊ix​⌋，贡献值则为 ⌊ x i ⌋ − ⌊ x ⌋ \lfloor {x\over{i}} \rfloor-\lfloor\sqrt x\rfloor ⌊ix​⌋−⌊x ​⌋

举个例子，比如求 1 → 10 1\to 10 1→10 的因数个数和，则有下面的过程：

1. 首先是看 1 1 1 的贡献，为 10 / 1 10/1 10/1，共有 10 10 10 个数有 1 1 1 这个因子
2. 然后是找 1 × m 1\times m 1×m，满足要求的数字有 1 × 4 , 1 × 5 , … 1 × 10 1\times 4,1\times 5,\dots 1\times 10 1×4,1×5,…1×10，共 7 7 7 个
3. 看 2 2 2 的贡献，为 10 / 2 10/2 10/2，共有 5 5 5 个数有 2 2 2 这个因子
4. 然后有 2 × 4 , 2 × 5 2\times 4,2\times 5 2×4,2×5，共 2 2 2 个
5. 然后看 3 3 3 的贡献，为 10 / 3 10/3 10/3，共有 3 3 3 个数有 3 3 3 这个因子
6. 然后由于 3 × 4 > 10 3\times 4>10 3×4>10，所以共 0 0 0 个
7. 综上，总的因数个数和为 10 + 7 + 5 + 2 + 3 + 0 = 27 10+7+5+2+3+0=27 10+7+5+2+3+0=27

代码

#include <math.h>
#include <stdio.h>
typedef long long LL;

/**
 * @brief 计算 1 到 n 的因子个数和
 *
 * @param n
 * @return LL
 */
LL fact_cnt(int n) {
    LL res = 0;
    int s = sqrt(n);
    for (int i = 1; i * i <= n; i++) {
        // res += n / i;
        // res += n / i - s;
        // 下面这句是上面两句的合并
        res += (n / i << 1) - s;
    }
    return res;
}

int main(void) {
    int q = 0, n = 0;
    scanf("%d", &q);
    while (q--) {
        scanf("%d", &n);
        printf("%lld\n", fact_cnt(n));
    }
    return 0;
}