【数学】因数平方和【蓝桥杯】

题目

因数平方和 - 蓝桥云课

4662. 因数平方和 - AcWing题库

---

问题描述

记 $f(x)$ 为 $x$ 的所有因数的平方的和。例如: $f(12)=1^{2}+2^{2}+3^{2}+4^{2}+6^{2}+$ $12^{2}$

定义 $g(n)=\sum_{i=1}^{n} f(i)$ 。给定 $n$ , 求 $g(n)$ 除以 $10^{9}+7$ 的余数。

输入格式

输入一行包含一个正整数 $n$ 。

输出格式

输出一个整数表示答案 $g(n)$ 除以 $10^{9}+7$ 的余数。

样例输入

100000

样例输出

680584257

评测用例规模与约定

对于 $20 \%$ 的评测用例, $n \leq 10^{5}$ 。

对于 $30 \%$ 的评测用例, $n \leq 10^{7}$ 。

对于所有评测用例, $1 \leq n \leq 10^{9}$ 。

运行限制

• 最大运行时间：1s
• 最大运行内存: 512M

解题

方法一：暴力 枚举 (20%)

思路

最简单直接的暴力做法，对 $1 \sim n$ 中每个数求因子平方和并累和。

求一个数的所有因子用到了试除法求约数。

$O(n\log{n})$ 的时间复杂度很明显只能过掉前 $20\%$ 的数据（ $1 \le n \le 10^5$ ）。

代码

import java.util.*;

public class Main {
    static final int MOD = (int) 1e9 + 7;
    
    static long f(int x) {
        long res = 0L;
        for (long i = 1; i <= x / i; ++i) {
            if (x % i == 0) {
                res = (res + i * i) % MOD;
                if (i * i == x) continue;
                long j = x / i;
                res = (res + j * j) % MOD;
            }
        }
        return res;
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long ans = 0;
        for (int i = 1; i <= n; ++i) ans = (ans + f(i)) % MOD;
        System.out.println(ans);
    }
}

方法二：数学 (30% ~ 100%)

思路

以 $n = 12$ 为例：

$$\begin{aligned} f(1) &= 1^2 &&\\ f(2) &= 1^2 + 2^2 &&\\ f(3) &= 1^2 \hspace{5ex} + 3^2 &&\\ f(4) &= 1^2 + 2^2 \hspace{5ex} + 4^2 &&\\ f(5) &= 1^2 \hspace{15ex} + 5^2 &&\\ f(6) &= 1^2 + 2^2 + 3^2 \hspace{10ex} + 6^2 &&\\ f(7) &= 1^2 \hspace{25ex} + 7^2 &&\\ f(8) &= 1^2 + 2^2 \hspace{5ex} + 4^2 \hspace{15ex} + 8^2 &&\\ f(9) &= 1^2 \hspace{5ex} + 3^2 \hspace{25ex} + 9^2 &&\\ f(10)&= 1^2 + 2^2 \hspace{10ex} + 5^2 \hspace{20ex} + 10^2 &&\\ f(11)&= 1^2 \hspace{45ex} + 11^2 &&\\ f(12)&= 1^2 + 2^2 + 3^2 + 4^2 \hspace{5ex} + 6^2 \hspace{25ex} + 12^2 &&\\ \end{aligned}$$

很明显的发现 $1 \sim 12$ 所有数都以因子的形式出现，只是出现的次数有所不同，所以我们可以从因子的角度来理解问题：

• 因子 $1$ 出现在 $1 \sim 12$ ，共 $12$ 个数中；
• 因子 $2$ 出现在 $2, 4, 6, 8, 10, 12$ ，共 $6$ 个数中；
• 因子 $3$ 出现在 $3, 6, 9, 12$ ，共 $4$ 个数中；
• 因子 $4$ 出现在 $4, 8, 12$ ，共 $3$ 个数中；
• 因子 $5$ 出现在 $5, 10$ ，共 $2$ 个数中；
• 因子 $6$ 出现在 $6, 12$ ，共 $2$ 个数中；
• 因子 $7$ 出现在 $7$ ，共 $1$ 个数中；
• …
• 因子 $12$ 出现在 $12$ ，共 $1$ 个数中。

很符合直觉，也很符合数学地总结出规律：因子 $i$ 在 $1 \sim n$ 中出现在 $i$ 的倍数中，出现次数为 $\lfloor \frac{n}{i} \rfloor$ ，所以因子 $i$ 可以对 $g(n)$ 提供的贡献为 $i^2 \times \lfloor \frac{n}{i} \rfloor$。

那么就有： $g(n) = \sum_{i=1}^{n} i^2 \times \lfloor \frac{n}{i} \rfloor$ 。

推到这一步，我们把时间复杂度降到了 $O(n)$ ，可以过前 $30\%$ 的数据（ $1 \le n \le 10^7$ ）了。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int MOD = (int) 1e9 + 7;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long ans = 0L;
        for (long i = 1; i <= n; ++i) {
            ans = (ans + (n / i) * (i * i)) % MOD;
        }
        System.out.println(ans);
    }
}

优化

观察 $g(n) = \sum_{i=1}^{n} i^2 \cdot \lfloor \frac{n}{i} \rfloor$ ，当 $n = 12$ 时：

$$\begin{aligned} i &\hspace{2em}= \hspace{2em} 1 \quad\enspace 2 \quad 3 \quad 4 \quad 5 \quad 6 \quad 7 \quad 8 \quad 9 \quad 10 \quad 11 \quad 12 &&\\ \lfloor \frac{n}{i} \rfloor &\hspace{2em}=\hspace{2em} \underline{12} \quad \underline{6} \quad \underline{4} \quad \underline{3} \quad \underline{2 \quad 2} \quad \underline{1 \quad 1 \quad 1 \quad 1 \quad\enspace 1 \quad\enspace 1} &&\\ & \hspace{15em} l \hspace{8em} r \end{aligned}$$

很容易发现 $\lfloor \frac{n}{i} \rfloor$ 是按块状分布的，对于元素相同的 $[l, r]$ 一块（例见上） ：

$$\begin{aligned} \sum_{i=l}^{r} i^2 \cdot \lfloor \frac{n}{i} \rfloor &= \lfloor \frac{n}{i} \rfloor \sum_{i=l}^{r} i^2 &&\\ &= \lfloor \frac{n}{i} \rfloor (\sum_{i=1}^{r} i^2 - \sum_{i=1}^{l-1} i^2) \end{aligned}$$

其中： $1\sim n$ 的平方和可以由平方和公式：$\sum_{i=1}^{n} i^2 = 1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}$ 很容易的以 $O(1)$ 的时间复杂度算出来。

但是我们注意到，分式的被除数中 $n, n+1, 2n+1$ 都是可以取到 $10^9$ 的大数，所以每乘一次都应该对 $10^9+7$ 取模以防止越界。但这是一个除法，如果被除数取模后再除会导致结果错误，所以应该利用 $6$ 的逆元把除法变为乘法再计算。

对于 $l$ ，如何求 $r$ ？根据数论分块的结论：

对于常数 $n$ ，使得式子 $\left\lfloor \frac{n}{l} \right\rfloor = \left\lfloor \frac{n}{r} \right\rfloor$ 成立的最大的满足 $1 \le r \le n$ 的 $r$ 的值为 $\left\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\right\rfloor$。
即值 $\left\lfloor \frac{n}{l} \right\rfloor$ 所在的块的右端点为 $\left\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\right\rfloor$ 。

时间复杂度：$O(\sqrt{n})$ ，可以过 $100\%$ 的数据（ $1 \le n \le 10^9$ ）。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int MOD = (int) 1e9 + 7;
    static long inv;
    // 快速幂用于求逆元
    static long quickPow(long base, long exp, long mod) {
        long res = 1L;
        while (exp > 0) {
            if ((exp & 1) == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp >>= 1;
        }
        return res;
    }
    // 平方和公式 每一步都要取模
    static long s(long n) {
        return n * (n + 1) % MOD * (2 * n + 1) % MOD * inv % MOD;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long ans = 0L;
        // 求6在模MOD意义下的逆元
        inv = quickPow(6, MOD - 2, MOD);
        for (int l = 1; l <= n;) {
            // x: 当前块中的相同值  r: 当前块的右边界
            int x = n / l, r = n / (n / l);
            ans = ((ans + x * (s(r) - s(l - 1))) % MOD + MOD) % MOD;
            l = r + 1;
        }
        System.out.println(ans);
    }
}

$6$ 是常量， $6$ 的逆元自然也是常量，直接硬编码也可以：

import java.util.*;
import java.io.*;

public class Main {
    static final int MOD = (int) 1e9 + 7;
    static final int INV = 166666668;

    static long s(long n) {
        return n * (n + 1) % MOD * (2 * n + 1) % MOD * INV % MOD;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long ans = 0L;
        for (int l = 1; l <= n;) {
            int x = n / l, r = n / (n / l);
            ans = ((ans + x * (s(r) - s(l - 1))) % MOD + MOD) % MOD;
            l = r + 1;
        }
        System.out.println(ans);
    }
}