标签 数论分块 下的文章

「2019 Multi-University Training Contest 1」Function

题目链接：HDU 6588（加强版 LOJ 6686）

本文为加强版题解。

给定正整数 $n$，请你求如下式子的值：

$$ \sum_{i = 1} ^ {n} \gcd(\left\lfloor\sqrt[3]{i}\right\rfloor,i) $$

答案对 $998244353$ 取模。

数据范围：$1 \le n \le 10 ^ {30}$。

「SDOI 2017」数字表格

题目链接：LOJ 2000

Doris 刚刚学习了 $\text{Fibnacci}$ 数列，用 $f[i]$ 表示数列的第 $i$ 项，那么：

$$ \begin{align*} f[0] &= 0 \\ f[1] &= 1 \\ f[n] &= f[n - 1] + f[n - 2], n \ge 2 \end{align*} $$

Doris 用老师的超级计算机生成了一个 $n \times m$ 的表格，第 $ i $ 行第 $ j $ 列的格子中的数是 $f[\gcd(i, j)]$，其中 $\gcd(i, j)$ 表示 $i$ 与 $j$ 的最大公约数。

Doris 的表格中共有 $ n \times m $ 个数，她想知道这些数的乘积是多少。

这些数的乘积实在是太大了，所以 Doris 只想知道乘积对 $10 ^ 9 + 7$ 取模后的结果。

本题有 $T$ 组数组。

数据范围：$1 \le T \le 1000$，$1 \le n, m \le 10 ^ 6$。

「CQOI 2015」选数

题目链接：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」这是一道简单的数学题

题目链接：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$。

「算法笔记」杜教筛

「JSOI 2016」灯塔

题目链接：LOJ 2074

JSOI 的国境线上有 $N$ 座连续的山峰,其中第 $i$ 座的高度是 $h_i$。为了简单起见,我们认为这 $n$ 座山峰排成了连续一条直线。

如果在第 $i$ 座山峰上建立一座高度为 $p(p \ge 0)$ 的灯塔，JYY 发现,这座灯塔能够照亮第 $j$ 座山峰,当且仅当满足如下不等式：

$$ h_j \le h_i + p - \sqrt{\vert i − j\vert} $$

JSOI国王希望对于每一座山峰，JYY 都能提供建造一座能够照亮全部其他山峰的灯塔所需要的最小高度。你能帮助 JYY 么？

数据范围：$1< n\le 10 ^ 5$，$0< h_i \le 10 ^ 9$。