标签 积性函数 下的文章

「LOJ 6229」这是一道简单的数学题

题目链接：LOJ 6229

这是一道非常简单的数学题。

最近 LzyRapx​ 正在看 mathematics for computer science 这本书，在看到数论那一章的时候，LzyRapx 突然想到这样一个问题。

设

$$ F(n) = \sum_{i = 1} ^ n \sum_{j = 1} ^ i \frac{\operatorname{lcm}(i, j)}{\gcd(i, j)} $$

其中，$\operatorname{lcm}(a, b)$ 表示 $a$ 和 $b$ 的最小公倍数，$\gcd(a, b)$ 表示 $a$ 和 $b​$ 的最大公约数。

给定 $n$ ，让你求： $F(n) \bmod (10 ^ 9 + 7)​$。

数据范围：$1 \le n \le 10 ^ 9$。

「算法笔记」杜教筛

「Luogu 5106」dkw 的 lcm

题目链接：Luogu 5106

善良的 dkw 决定直接告诉你题面：

$$ \prod_{i_1 = 1} ^ n \prod_{i_2 = 1} ^ n \cdots\prod_{i_k = 1} ^ n \varphi(\operatorname{lcm}(i_1, i_2, \cdots, i_k)) $$

请你求上述式子，答案对 $10 ^ 9 + 7$ 取模。

其中 $\operatorname{lcm}(i_1, i_2, \cdots, i_k)$ 表示这 $k$ 个数的最小公倍数。特别地，一个数的 $\operatorname{lcm}$ 是自身。

数据范围：$1\le n,k\le 10^6$。