转到我的博客阅读：【数学】因数平方和【蓝桥杯】

因数平方和 - 蓝桥云课

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$ 的余数。

样例输入

样例输出

评测用例规模与约定

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

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

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

运行限制

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

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

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