GMOJ J2479 【数论】

Description

定义数论函数 $\lambda(n)$ 为：

• 设 $n$ 的质因数分解为 $n = \prod {p_i}^{e_i}$，则 $\lambda(n) = (-1)^{\sum_{e_i}}$。

试求：

$$\sum_{k = 1}^n \sum_{i|k} \sum_{j|i} \lambda(i)\lambda(j)$$

答案对 $998244353$ 取模。

$$1 \leq n \leq 10^{12}$$

Solution

考虑套路的挪一下 $\sum$ 的位置：

$$\sum_{k = 1}^n \sum_{i|k} \sum_{j|i} \lambda(i)\lambda(j) = \sum_{k = 1}^n \sum_{i|k} \lambda(i) [\sum_{j|i} \lambda(j)]$$

令 $g(i) = \sum_{j|i} \lambda(j)$，则原式等于 $\sum_{k = 1}^n \sum_{i|k} \lambda(i) g(i)$。

令 $d = i$，则原式可进一步化为 $\sum_{k = 1}^n \sum_{d|k} \lambda(d) g(d)$。

考虑枚举 $d$，则这个式子的值等于 $\sum_{d = 1}^n \lambda(d) g(d) \lfloor \dfrac{n}{d} \rfloor$。

由于 $\lfloor \dfrac{n}{d} \rfloor$ 显然最多只有 $\sqrt{n}$ 种取值，然后我们又发现 $\lambda(d) g(d)$ 的前缀和是可以 $O(1)$ 求的，那么就可以随便算咯。

话说我上一次在考场上独立推出数论题还是一两年前的事情。

其实这题有人打表玩出来了，答案也可以写为 $\sum_{i = 1}^{\lfloor \sqrt{n} \rfloor} \lfloor \dfrac{n}{i^2} \rfloor$。

Code

#include <cstdio>
#include <cmath>
#define mod 998244353
long long sum (long long n)
{
	return sqrt(n);
}
int main ()
{
	long long Ans = 0, n = 0;
	scanf("%lld", &n);
	long long l = n / 2 + 1, r = n, cc = 2;
	long long A = sqrt(n);
	long long ll = l, rr = r;
	while(l > A && r > A)
	{
		ll = l, rr = r;
		Ans += (sum(r) - sum(l - 1)) * (n / l);
		Ans %= mod;
		r = l - 1, cc++;
		l = (n / cc) + 1;
	}
	for(long long i = 1;i < ll; i++)
	{
		Ans += (sum(i) - sum(i - 1)) * (n / i);
		Ans %= mod;
	}
	printf("%lld", Ans);
	return 0;
}