题意描述

洛谷链接

给定 \(n\)，求

\[\sum_{i = 1}^n \sum_{j = i + 1}^n \gcd(i, j)\]

其中 \(\gcd(i, j)\) 表示 \(i\) 和 \(j\) 的最大公约数。

数据范围：\(2 \leq n \leq 2 \times 10^6\)。

题意描述

Codeforces 链接

你有一个本子，你要往上面写全部的长度为 \(n\) 的 \(b\) 进制数字，每一页可以写 \(c\) 个。要求所有数字必须严格不含前导 \(0\)。求最后一页上有多少个数字

数据范围：\(2 \leq b < 10^{10^6}, 1 \leq n < 10^{10^6}, 1 \leq c \leq 10^9\)

题意描述

洛谷链接

小 Z 是一个小有名气的钢琴家，最近 C 博士送给了小 Z 一架超级钢琴，小 Z 希望能够用这架钢琴创作出世界上最美妙的音乐。

这架超级钢琴可以弹奏出 \(n\) 个音符，编号为 \(1\) 至 \(n\)。第 \(i\) 个音符的美妙度为 \(A_i\)，其中 \(A_i\) 可正可负。

一个“超级和弦”由若干个编号连续的音符组成，包含的音符个数不少于 \(L\) 且不多于 \(R\)。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两个超级和弦被认为是相同的，当且仅当这两个超级和弦所包含的音符集合是相同的。

小 Z 决定创作一首由 \(k\) 个超级和弦组成的乐曲，为了使得乐曲更加动听，小 Z 要求该乐曲由 \(k\) 个不同的超级和弦组成。我们定义一首乐曲的美妙度为其所包含的所有超级和弦的美妙度之和。小 Z 想知道他能够创作出来的乐曲美妙度最大值是多少。

数据范围：\(-1000 \leq A_i \leq 1000\)，\(1 \leq L \leq R \leq n\) 且保证一定存在满足要求的乐曲。

题意描述

洛谷链接

约翰到商场购物，他的钱包里有 \(k (1 \le k \le 16)\) 个硬币，面值的范围是 \(1 \sim 10^8\)。

约翰想按顺序买 \(n\) 个物品 \((1 \le n \le 10^5)\)，第 \(i\) 个物品需要花费 \(c_i\) 块钱，\((1 \le c_i \le 10^4)\)。

在依次进行的购买 \(n\) 个物品的过程中，约翰可以随时停下来付款，每次付款只用一个硬币，支付购买的内容是从上一次支付后开始到现在的这些所有物品（前提是该硬币足以支付这些物品的费用）。不幸的是，商场的收银机坏了，如果约翰支付的硬币面值大于所需的费用，他不会得到任何找零。

请计算出在购买完 \(n\) 个物品后，约翰最多剩下多少钱。如果无法完成购买，输出 \(-1\)。

题意描述

洛谷链接

给定一张 \(t\) 条边的无向连通图，求从 \(s\) 到 \(e\) 经过 \(n\) 条边的最短路长度。

数据范围：\(1 \le n \le 10^6\)、\(2 \le t \le 100\)、\(1 \le s, t \le 1000\)。

由于某些原因某 OIer 零基础学习 CTF 被打爆了 QWQ

本文一切例题均可在 CTFHub 找到。

每一个少年终将梦醒

参加了最后一次 OI 系列的考试，终于也 AFO 了。几年伴随我的 OI 历程也在此结束。梦结束了。

接下来 whk 加油！

题意描述

平面直角坐标系的第一象限内有一块左下角为 \((0,0)\) 右上角为 \((10^{100},10^{100})\) 的矩形区域，区域内有正偶数个整点，试求出这样一条从 \((0,0)\) 出发，到 \((10^{100},10^{100})\) 的在区域内部的折线：

• 折线的每一部分都平行于 \(x\) 轴或 \(y\) 轴。
• 折线不能经过给定的整点。
• 折线将整块区域分成包含给定整点个数相等的两块。
• 折线拥有尽可能少的折点。

可以证明一定存在一条满足限制的折线，你只需要输出满足限制的折线的折点数即可。

注意折点的坐标可以不是整数。

每组测试点有 \(T\) 组数据，对于所有测试点，\(1 \leq T \leq 10^4\)，\(1 \leq \sum n \leq 5 \times 10^5\)，\(1 \leq n \leq 10^5\)，\(1 \leq x_i,y_i \leq n\)，保证 \(n\) 为正偶数，每组数据中不存在两个坐标相同的整点。

题意描述

洛谷链接

Farmer John（又）想到了一个新的奶牛晨练方案！
如同之前，Farmer John 的 \(N\) 头奶牛站成一排。对于 \(1\le i\le N\) 的每一个 \(i\)，从左往右第 \(i\) 头奶牛的编号为 \(i\)。他告诉她们重复以下步骤，直到奶牛们与她们开始时的顺序相同。

给定长为 \(N (1 \le N \le 10^4)\) 的一个排列 \(A\)，奶牛们改变她们的顺序，使得在改变之前从左往右第 \(i\) 头奶牛在改变之后为从左往右第 \(A_i\) 头。
例如，如果 \(A=(1,2,3,4,5)\)，那么奶牛们总共进行一步。如果 \(A=(2,3,1,5,4)\)，那么奶牛们总共进行六步。每步之后奶牛们从左往右的顺序如下：

0 步：\((1,2,3,4,5)\)
1 步：\((3,1,2,5,4)\)
2 步：\((2,3,1,4,5)\)
3 步：\((1,2,3,5,4)\)
4 步：\((3,1,2,4,5)\)
5 步：\((2,3,1,5,4)\)
6 步：\((1,2,3,4,5)\)
求所有正整数 \(K\) 的和，使得存在一个长为 \(N\) 的排列，奶牛们需要进行恰好 \(K\) 步。

由于这个数字可能非常大，输出答案模 \(M\) 的余数（\(10^8\le M\le 10^9+7\)，\(M\) 是质数）。

题意描述

洛谷连接

一共有 \(n\) 个飞行员，其中有 \(m\) 个外籍飞行员和 \((n - m)\) 个英国飞行员，外籍飞行员从 \(1\) 到 \(m\) 编号，英国飞行员从 \(m + 1\) 到 \(n\) 编号。 对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

对于 \(100\%\) 的数据，保证 \(1 \leq m \leq n < 100\)，\(1 \leq u \leq m < v \leq n\)，同一组配对关系只会给出一次。