标签 数论 下的文章
- 首页
- 数论
「Codeforces 1228E」Another Filling the Grid
题目链接：Codeforces 1228E
你有一个 $n \times n$ 的网格和一个整数 $k$，在每个格子中都填入一个整数，满足如下条件：
- 所有格子中的整数都介于 $1$ 到 $k$ 之间。
- 第 $i$ 行的最小值为 $1$（$1 \le i \le n$）。
- 第 $j$ 列的最小值为 $1$（$1 \le j \le n$）。
请求出填数的方案数，答案对 $10 ^ {9} + 7$ 取模。
数据范围：$1 \le n \le 250$，$1 \le k \le 10 ^ {9}$。
「Codeforces 1204E」Natasha, Sasha and the Prefix Sums
题目链接：Codeforces 1204
Natasha 最喜欢的数字是 $n$ 和 $1$，Sasha 最喜欢的数字是 $m$ 和 $-1$。某一天他们写下了长度为 $n + m$ 且包含恰好 $n$ 个 $1$ 和 $m$ 个 $-1$ 的所有可能的序列。对于每一个序列计算出它的最大前缀和（允许为空）；形式化地，我们定义 $f(a)$ 表示序列 $a_{1, \dots, l}(l \le 0)$ 的最大前缀和，那么有：
$$ f(a) = \max \left (0, \max _ {i = 1} ^ {l} \sum _ {j = 1} ^ {i} a_{j} \right ) $$
现在他们想要对于所有满足条件的序列，求出 $f(a)$ 的总和。答案对 $998244853$ 取模。
数据范围：$0 \le n, m \le 2000$。
「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}$。
「SPOJ 16607」IE1 - Sweets
题目链接：SPOJ 16607
John 有 $n$ 个水果罐子，每个罐子都装有不同种类的糖果，第 $i$ 个罐子里有 $m_i$ 个糖果。John 决定吃一些糖果，并且打算至少吃 $a$ 个，至多吃 $b$ 个，求一共有多少种吃法。答案对 $2004$ 取模。
数据范围：$1 \le n \le 10$，$0 \le a \le b \le 10 ^ 7$，$0 \le m_i \le 10 ^ 7$。
「Codeforces 1186E」Vus the Cossack and a Field
题目链接：Codeforces 1186E
Vus 有一个 $n \times m$ 的 $01$ 矩阵，他通过如下方法构造了一个无限大的矩阵：
- 计算出当前矩阵的反矩阵。即 $0$ 变成 $1$，$1$ 变成 $0$。
- 将当前矩阵放在左上角和右下角，将反矩阵放在左下角和右上角。
- 将得到的矩阵作为当前矩阵，回到步骤 $1$ 并不断重复。
我们将列从上到下标号为 $1$ 到 $\infty$，将行从左到右标号为 $1$ 到 $\infty$。接下来进行 $q$ 次询问，每次询问子矩阵 $(x_1, y_1, x_2, y_2)$ 的元素之和。
数据范围：$1 \le n, m \le 1000$，$1 \le q \le 10 ^ 5$，$1 \le x_1 \le x_2 \le 10 ^ 9$，$1 \le y_1 \le y_2 \le 10 ^ 9$。
「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$。