题目陈述

大意：给定一个正整数$nn$n，$nn$n表示为$n=p\times k+mn=p\backslash times\; k\; +\; m$n=p×k+m。即，$nn$n充当被除数，对于$p,1\le p\le np,1\; \backslash leq\; p\; \backslash leq\; n$p,1≤p≤n，充当除数，然后得到对应的余数$mm$m，求对于所有的除数$p（1\le p\le n）p（1\; \backslash leq\; p\; \backslash leq\; n）$p（1≤p≤n）的商$kk$k与余数$mm$m的乘积之和，即${\sum }_{k=\lfloor n/p\rfloor }k\ast m\backslash sum\_\{k=\backslash lfloor\; n/p\backslash rfloor\}\; k*m$∑k=⌊n/p⌋​k∗m，答案取模$modmod$mod

算法一：朴素算法

算法思路

• 根据题意，一个很显然的算法，就是对于每一个$pp$p分别计算出他的$k,mk,m$k,m然后计算$k\ast mk*m$k∗m

代码实现

class Solution {
public:
    long long cowModCount(long long n) {
        long long ans = 0, mod = 1e9 + 7, k, m;
        for (int p = 1; p <= n; p ++ ) //枚举所有合法的p
        {
            k = n / p; //求解商
            m = n % p; //求解余数
            ans = (ans + k * m % mod) % mod; //将他们的贡献加入到答案中
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度，每个合法的$pp$p都遍历了一遍，即为$pp$p的区间大小，时间复杂度为$O\left(n\right)O(n)$O(n)，当然$n_{max}=INT\_MAXn\_\{max\}=INT\backslash \_MAX$nmax​=INT_MAX，显然还是会$TLETLE$TLE的
• 空间复杂度，定义了四个变量$ans,mod,k,mans,mod,k,m$ans,mod,k,m，为$O\left(1\right)O(1)$O(1)

算法二：数学推导+整除分块

前置知识：整除分块

• 此处我们我们需要先了解一个前置知识：整除分块。
• 首先，要了解整除分块是干什么的？设计整除分块的题目大概都具有以下形式 ${\sum }_{i=1}^n\lfloor {\displaystyle \frac{n}{i}}\rfloor \backslash sum\_\{i=1\}^n\; \backslash lfloor\; \backslash cfrac\{n\}\{i\}\backslash rfloor$∑i=1n​⌊in​⌋
• 上面的括号代表向下取整，即整除
• 我们以$n=6n=6$n=6为例子
• 我们可以发现对于一个$ii$i，往往是一段区间的整除值都是同一个值（废话）
• 假如我们通常知道了区间内的一个下标（一般是左端点），如何求得跟它所在区间的右端点？
• 设$n=i\ast j+t，t\in [0,i-1]n=i*j+t，t\backslash in\; [0,i-1]$n=i∗j+t，t∈[0,i−1]，显然我们可以这样表示$ii$i，而把$jj$j设置为倍数
• 对于右端点$rr$r,必然有t<j
• 反证法，若$t>=jt>=j$t>=j则，可以令$t^{\prime }=t-jt\text{'}=t-j$t′=t−j,$n=r\ast j+t=(r+1)\ast j+t^{\prime }n=r*j+t=(r+1)*j+t\text{'}$n=r∗j+t=(r+1)∗j+t′
• 就得到了区间内比右端$rr$r还靠右的满足条件的点
• 所以：对于右端点$rr$r,必然有t<j
• 我们就可以根据这个性质，通过$ll$l，求得$jj$j，再通过$jj$j求得$rr$r
• 故对于一个区间，我们知道左端点$ll$l，即可以通过公式计算右端点$r=\lfloor {\displaystyle \frac{n}{\lfloor {\displaystyle \frac{n}{l}}\rfloor }}\rfloor r\; =\; \backslash lfloor\; \backslash cfrac\{n\}\{\backslash lfloor\; \backslash cfrac\{n\}\{l\}\backslash rfloor\}\backslash rfloor$r=⌊⌊ln​⌋n​⌋，代码中写作r = n / (n / i)，注意此处为整除
• 时间复杂度为$O\left(\sqrt{n}\right)O(\backslash sqrt\; n)$O(n​)

算法思路

• 显然这是一道数学题，我们考虑数学方法，当然，也少不了推导和化简
• 对于所有的$p,(p\in [1,n\left]\right)p,(p\backslash in[1,n])$p,(p∈[1,n])
• 有$ans=\sum \lfloor {\displaystyle \frac{n}{p}}\rfloor \times \left(n\%p\right)ans\; =\backslash sum\; \backslash lfloor\; \backslash cfrac\{n\}\{p\}\backslash rfloor\; \backslash times\; (n\; \backslash \%\; p)$ans=∑⌊pn​⌋×(n%p)
• 即 $ans={\sum }_{p=1}^n\lfloor {\displaystyle \frac{n}{p}}\rfloor \times (n-p\times \lfloor {\displaystyle \frac{n}{p}}\rfloor )ans=\backslash sum\_\{p=1\}^\{n\}\; \backslash lfloor\; \backslash cfrac\{n\}\{p\}\backslash rfloor\; \backslash times\; (n\; -\; p\; \backslash times\; \backslash lfloor\; \backslash cfrac\{n\}\{p\}\backslash rfloor)$ans=∑p=1n​⌊pn​⌋×(n−p×⌊pn​⌋)
• 整除分块思想有，$k\in [l,r]k\; \backslash in[l,r]$k∈[l,r],其中$r=\lfloor {\displaystyle \frac{n}{\lfloor {\displaystyle \frac{n}{l}}\rfloor }}\rfloor r\; =\; \backslash lfloor\; \backslash cfrac\{n\}\{\backslash lfloor\; \backslash cfrac\{n\}\{l\}\backslash rfloor\}\backslash rfloor$r=⌊⌊ln​⌋n​⌋
• 同一块$\lfloor {\displaystyle \frac{n}{k}}\rfloor \backslash lfloor\; \backslash cfrac\{n\}\{k\}\backslash rfloor$⌊kn​⌋都相同，即$\lfloor {\displaystyle \frac{n}{k}}\rfloor =\lfloor {\displaystyle \frac{n}{l}}\rfloor \backslash lfloor\; \backslash cfrac\{n\}\{k\}\backslash rfloor=\backslash lfloor\; \backslash cfrac\{n\}\{l\}\backslash rfloor$⌊kn​⌋=⌊ln​⌋
• 故对于同一块有${\sum }_{k=l}^r\lfloor {\displaystyle \frac{n}{l}}\rfloor \times (n-k\times \lfloor {\displaystyle \frac{n}{l}}\rfloor )\backslash sum\_\{k=l\}^\{r\}\; \backslash lfloor\; \backslash cfrac\{n\}\{l\}\backslash rfloor\; \backslash times\; (n-k\; \backslash times\; \backslash lfloor\; \backslash cfrac\{n\}\{l\}\backslash rfloor)$∑k=lr​⌊ln​⌋×(n−k×⌊ln​⌋)
• 展开括号得 ${\sum }_{k=l}^r(n\times \lfloor {\displaystyle \frac{n}{l}}\rfloor -k\times \lfloor {\displaystyle \frac{n}{l}}{\rfloor }^2)\backslash sum\_\{k=l\}^\{r\}(n\backslash times\; \backslash lfloor\; \backslash cfrac\{n\}\{l\}\backslash rfloor-k\backslash times\backslash lfloor\; \backslash cfrac\{n\}\{l\}\backslash rfloor\; ^2)$∑k=lr​(n×⌊ln​⌋−k×⌊ln​⌋2)
• 求和符号性质有 ${\sum }_{k=l}^{r}n\times \lfloor {\displaystyle \frac{n}{l}}\rfloor -{\sum }_{k=l}^{r}k\times \lfloor {\displaystyle \frac{n}{l}}{\rfloor }^2\backslash sum\_\{k=l\}^\{r\}n\backslash times\; \backslash lfloor\; \backslash cfrac\{n\}\{l\}\backslash rfloor\; -\backslash sum\_\{k=l\}^\{r\}k\backslash times\; \backslash lfloor\; \backslash cfrac\{n\}\{l\}\backslash rfloor^2$∑k=lr​n×⌊ln​⌋−∑k=lr​k×⌊ln​⌋2
• 令$len=r-l+1len=r-l+1$len=r−l+1
• 化简求和结果，等差数列公式有 $len\times n\times \lfloor {\displaystyle \frac{n}{l}}\rfloor -{\displaystyle \frac{(l+r)\times len}{2}}\times k\times \lfloor {\displaystyle \frac{n}{l}}{\rfloor }^{2}len\backslash times\; n\; \backslash times\; \backslash lfloor\; \backslash cfrac\{n\}\{l\}\backslash rfloor\; -\; \backslash cfrac\{(l+r)\backslash times\; len\}\{2\}\backslash times\; k\; \backslash times\; \backslash lfloor\; \backslash cfrac\{n\}\{l\}\backslash rfloor^2$len×n×⌊ln​⌋−2(l+r)×len​×k×⌊ln​⌋2
• 现在已知每一块的$O\left(1\right)O(1)$O(1)求法
• 整除分块得到了每一块的答案即可求得$ansans$ans
• 下面是我的手写推导过程

关于不用逆元

• 肯定有同学好奇为什么我代码里面除了$22$2，但是没有用逆元？
• 因为那一整项求和公式，必然能整除2，故不需要逆元
• 证明如下：
• 只要$(l+r)(l+r)$(l+r)和$lenlen$len中有一个为偶数，就可以整除2
• $l,rl,r$l,r奇偶性相同时候，$(l+r)(l+r)$(l+r)为偶数，$len=r-l+1len=r-l+1$len=r−l+1为奇数，能整除
• $l,rl,r$l,r奇偶性不同的时候,$(l+r)(l+r)$(l+r)为奇数，$len=r-l+1len=r-l+1$len=r−l+1为偶数，能整除
• 故此处不需要用到逆元

复杂度分析

• 时间复杂度，整除分块为$O\left(\sqrt{n}\right)O(\backslash sqrt\; n)$O(n​)，对于每一块表达式求值为$O\left(1\right)O(1)$O(1)，总得时间复杂度为$O\left(\sqrt{n}\right)O(\backslash sqrt\; n)$O(n​)
• 空间复杂度，定义了几个变量，为$O\left(1\right)O(1)$O(1)

代码实现

class Solution {
public:
    long long cowModCount(long long n) {
        long long ans = 0, mod = 1e9 + 7;
        for (long long l = 1, r, len, tmp; l <= n; l = r + 1)
        {
            tmp = n / l;//重复计算所以用tmp暂存
            r = n / tmp;//根据公式计算右边界
            len = r - l + 1;//计算区间长度
            ans = (ans + len * tmp * n % mod - tmp * tmp % mod * (l + r) * len / 2 % mod) % mod;
        }//根据我们上面计算的公式，累加到ans值上面
        if (ans < 0)
            ans += mod;//C++里面负数取模依旧为负数，需要加上mod
        return ans;
    }
};