侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

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

GabrielxD
2023-03-05 / 0 评论 / 9 点赞 / 584 阅读 / 2,249 字
温馨提示:
本文最后更新于 2023-03-22,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

因数平方和 - 蓝桥云课

4662. 因数平方和 - AcWing题库


问题描述

f(x)f(x)xx 的所有因数的平方的和。例如: f(12)=12+22+32+42+62+f(12)=1^{2}+2^{2}+3^{2}+4^{2}+6^{2}+ 12212^{2}

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

输入格式

输入一行包含一个正整数 nn

输出格式

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

样例输入

100000

样例输出

680584257

评测用例规模与约定

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

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

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

运行限制

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

解题

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

思路

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

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

O(nlogn)O(n\log{n}) 的时间复杂度很明显只能过掉前 20%20\% 的数据( 1n1051 \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=12n = 12 为例:

f(1)=12f(2)=12+22f(3)=12+32f(4)=12+22+42f(5)=12+52f(6)=12+22+32+62f(7)=12+72f(8)=12+22+42+82f(9)=12+32+92f(10)=12+22+52+102f(11)=12+112f(12)=12+22+32+42+62+122\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}

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

  • 因子 11 出现在 1121 \sim 12 ,共 1212 个数中;
  • 因子 22 出现在 2,4,6,8,10,122, 4, 6, 8, 10, 12 ,共 66 个数中;
  • 因子 33 出现在 3,6,9,123, 6, 9, 12 ,共 44 个数中;
  • 因子 44 出现在 4,8,124, 8, 12 ,共 33 个数中;
  • 因子 55 出现在 5,105, 10 ,共 22 个数中;
  • 因子 66 出现在 6,126, 12 ,共 22 个数中;
  • 因子 77 出现在 77 ,共 11 个数中;
  • 因子 1212 出现在 1212 ,共 11 个数中。

很符合直觉,也很符合数学地总结出规律:因子 ii1n1 \sim n 中出现在 ii 的倍数中,出现次数为 ni\lfloor \frac{n}{i} \rfloor ,所以因子 ii 可以对 g(n)g(n) 提供的贡献为 i2×nii^2 \times \lfloor \frac{n}{i} \rfloor

那么就有: g(n)=i=1ni2×nig(n) = \sum_{i=1}^{n} i^2 \times \lfloor \frac{n}{i} \rfloor

推到这一步,我们把时间复杂度降到了 O(n)O(n) ,可以过前 30%30\% 的数据( 1n1071 \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)=i=1ni2nig(n) = \sum_{i=1}^{n} i^2 \cdot \lfloor \frac{n}{i} \rfloor ,当 n=12n = 12 时:

i=123456789101112ni=1264322111111lr\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}

很容易发现 ni\lfloor \frac{n}{i} \rfloor 是按块状分布的,对于元素相同的 [l,r][l, r] 一块(例见上) :

i=lri2ni=nii=lri2=ni(i=1ri2i=1l1i2)\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}

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

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

对于 ll ,如何求 rr ?根据数论分块的结论:

对于常数 nn ,使得式子 nl=nr\left\lfloor \frac{n}{l} \right\rfloor = \left\lfloor \frac{n}{r} \right\rfloor 成立的最大的满足 1rn1 \le r \le nrr 的值为 nnl\left\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\right\rfloor
即值 nl\left\lfloor \frac{n}{l} \right\rfloor 所在的块的右端点为 nnl\left\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\right\rfloor

时间复杂度:O(n)O(\sqrt{n}) ,可以过 100%100\% 的数据( 1n1091 \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);
    }
}

66 是常量, 66 的逆元自然也是常量,直接硬编码也可以:

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);
    }
}
9

评论区