龙哥的问题
解题思路:
本题要求 $\sum_{i=1}^N gcd(i,N)$,由于这里求的是一个求和,因此我们可以将要求的部分分成若干类。由于 $gcd(i,N)$ 一定是 $N$ 的约数,因此我们可以按照 $N$ 的约数进行分类。
对于 $N$ 的每个约数 $d$,我们看一下在 $1 \sim N$ 中有多少个数 $x$ 和 $N$ 的最大公约数是 $d$,也就是看一下有多少个数 $x$ 满足 $gcd(\frac{x}{d}, \frac{N}{d}) = 1$,设 $x’=\frac{x}{d},N’=\frac{N}{d}$,那么就是要求一下在 $1 \sim N’$ 中有多少个 $x’$ 和 $N’$ 互质,也就是 $\phi{(N’)}$,即 $\phi{(\frac{N}{d})}$。
因此本题的答案就是 $\sum_{d \vert N} d \cdot \phi{(\frac{N}{d})}$,到此已经能求出来了,如果直接枚举所有约数,然后求一下答案,那么应该是八千万的复杂度。
我们这里继续考虑优化,设 $d’=\frac{N}{d}$,则答案变成 $\sum_{d’\vert N} \frac{N}{d’} \phi(d’)$,然后将 $\phi(d’)$ 拆开,若 $d’$ 的约数分别是 $p_1\sim p_k$,则变成 $\sum_{d’\vert N} \frac{N}{d’} d’(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_k})$,然后将 $d’$ 约掉,把 $N$ 前移,得到 $N\sum_{d’\vert N} (1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_k})$
然后我们设 $N=p_1^{\alpha_1}p_2^{\alpha_2}…p_k^{\alpha_k},d’=p_1^{\beta_1}p_2^{\beta_2}…p_k^{\beta_k}$,并且能保证 $\beta_i \leq \alpha_i$,而我们的答案中就是枚举 $N$ 的所有约数 $d’$,对于每个 $d’$,我们需要计算的就是它的不完整的欧拉函数,也就是看一下哪些 $\beta_i \geq 1$,将这些质数拿出来计算一下不完整的欧拉函数。
其实就是从所有的质因子中选出一些数来组成一个约数 $d’$,然后计算一下这个 $d’$ 的贡献,我们可以看一下组成所有约数的方案,对于 $p_1$,显然能选 $0 \sim \alpha_1$ 次,共有 $\beta_1+1$ 种选法,同理,$p_2$ 有 $\beta_2+1$ 种选法,以此类推,每个质因子的每种选法搭配在一起就能得到所有的约数,而在 $p_1$ 选 $0$ 次时,$p_1$ 对于当前构成约数 $d’$ 的贡献是 $1$,而在选 $1 \sim \beta_1$ 次中都是会有 $1-\frac{1}{p_1}$ 的贡献,其他质因子也是同理。所以根据乘法分配律,我们真正要求的所有约数的不完整的欧拉函数的和就是 $\big( 1+(1-\frac{1}{p_1})+…+(1-\frac{1}{p_1}) \big)…\big( 1+(1-\frac{1}{p_k})+…+(1-\frac{1}{p_k}) \big)$
因此我们真正要求的答案就是 $\sum_{i=1}^k(1+\alpha_i(1-\frac{1}{p_i}))$。这样我们要先将所有质因子预处理出来,时间复杂度是 $O(\sqrt{N})$ 的,枚举也是枚举所有质因子,因此总的时间复杂度也是 $O(\sqrt{N})$ 的,这样效率明显提高了。
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
int main()
{
int n;
scanf("%d", &n);
LL res = n; //记录答案
for(int i = 2; i <= n / i; i++)
if(n % i == 0)
{
int a = 0, p = i; //a 为质数个数、p 为质数
while(n % p == 0) n /= p, a++;
res = res * (p + (LL)a * p - a) / p; //公式进行了通分处理
}
if(n > 1) res = res * ((LL)n + n - 1) / n;
printf("%lld\n", res);
return 0;
}