「2019 Multi-University Training Contest 1」Function
本文为加强版题解。
给定正整数 $n$，请你求如下式子的值：
$$ \sum_{i = 1} ^ {n} \gcd(\left\lfloor\sqrt[3]{i}\right\rfloor,i) $$
答案对 $998244353$ 取模。
数据范围：$1 \le n \le 10 ^ {30}$。
本文为加强版题解。
给定正整数 $n$，请你求如下式子的值：
$$ \sum_{i = 1} ^ {n} \gcd(\left\lfloor\sqrt[3]{i}\right\rfloor,i) $$
答案对 $998244353$ 取模。
数据范围：$1 \le n \le 10 ^ {30}$。
题目链接：LOJ 2095
我们知道，从区间 $[L, H]$（$L$ 和 $H$ 为整数）中选取 $N$ 个整数，总共有 $(H - L + 1) ^ N$ 种方案。小 Z 很好奇这样选出的数的最大公约数的规律，他决定对每种方案选出的 $N$ 个整数都求一次最大公约数，以便进一步研究。然而他很快发现工作量太大了，于是向你寻求帮助。你的任务很简单，小 Z 会告诉你一个整数 $K$，你需要回答他最大公约数刚好为 $K$ 的选取方案有多少个。由于方案数较大，你只需要输出其除以 $10 ^ 9 + 7$ 的余数即可。
数据范围：$1 \le N, K \le 10 ^ 9$，$1 \le L \le H \le 10 ^ 9$，$H - L \le 10 ^ 5$。
题目链接：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$。