chen_zhe @ 2020-01-19 19:25:41
洛谷鼓励各位用户将大型比赛的试题或者洛谷上缺乏的模板题，在确认没有版权问题的情况下，提供给洛谷。但是因为此类贴子日益增多，严重影响了讨论版面，而且部分用户所提供的试题并不符合规定，故做出以下说明：
USACO，POI，Baltic OI 等），或者大型的网络公开赛（例如 Codeplus 等），但是不包含例如校内的网络模拟赛之类的试题。spj，则相对较易的部分必须自行完成。若实在有困难才可以征集。具体尺度由管理进行评判。同时，对于已在洛谷主题库中但不符合洛谷主题目题目规范的题目，我们鼓励用户进行更正，但也至少要达到绿勾级别。要求更正后的题面严格遵守规范，同样回复在本讨论下，为了方便管理员，请将题面使用代码框```括起来。
若有发现难度标签明显有问题（即对于普及-以及以下的题目相差两个档次，或者对于提高-以及以上难度相差一个档次），欢迎大家提供建议。请在本楼回复题号和应当修正的难度。
为了提高管理员的审核效率，本贴禁止任何无意义回复，所有无意义回复均会被删除，行为恶劣者将会禁言，但是可以询问说明中的问题。若为修复题目问题，建议带上链接以增加效率。
请不要@管理员，会有管理员不定期来本帖处理。
by LCuter @ 2020-01-22 21:50:23
类型：题面修改
P3172
#### 题目描述
我们知道，从区间 $[L,H]$（$L$ 和 $H$ 为整数）中选取 $N$ 个整数，总共有 $(H-L+1)^N$ 种方案。小 z 很好奇这样选出的数的最大公约数的规律，他决定对每种方案选出的 $N$ 个整数都求一次最大公约数，以便进一步研究。然而他很快发现工作量太大了，于是向你寻求帮助。你的任务很简单，小 z 会告诉你一个整数 $K$，你需要回答他最大公约数刚好为 $K$ 的选取方案有多少个。由于方案数较大，你只需要输出其除以 $1000000007$ 的余数即可。
#### 输入格式
输入一行，包含 $4$ 个空格分开的正整数，依次为 $N$，$K$，$L$ 和 $H$。
#### 输出格式
输出一个整数，为所求方案数。
#### 说明/提示
样例解释
所有可能的选择方案：$(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4)$。
其中最大公约数等于 $2$ 的只有 $3$ 组：$(2, 2), (2, 4), (4, 2)$。
对于 $100\%$ 的数据，$1\le N,K\le 10^9$，$1\le L\le H\le 10^9$，$H-L\le 10^5$。by LCuter @ 2020-01-22 21:56:02
类型：题面修改
P3312
#### 题目描述
有一张 $n\times m$ 的数表，其第 $i$ 行第 $j$ 列（$1\le i\le n$，$1\le j\le m$）的数值为能同时整除 $i$ 和 $j$ 的所有自然数之和。给定 $a$，计算数表中不大于 $a$ 的数之和。
#### 输入格式
**输入包含多组数据。**
输入的第一行一个整数 $Q$ 表示测试点内的数据组数
接下来 $Q$ 行，每行三个整数 $n$，$m$，$a$（$|a|\le 10^9$）描述一组数据。
#### 输出格式
对每组数据，输出一行一个整数，表示答案模 $2^{31}$ 的值。
#### 说明/提示
$1\le n,m\le 10^5$，$1\le Q\le 2\times 10^4$。by cmll02 @ 2020-01-23 10:22:55
类型：题面修改
题目：P1290 欧几里得的游戏
新题面：
### 题目描述
欧几里德的两个后代 Stan 和 Ollie 正在玩一种数字游戏，这个游戏是他们的祖先欧几里德发明的。给定两个正整数 $M$ 和 $N$，从 Stan 开始，从其中较大的一个数，减去较小的数的正整数倍，当然，得到的数不能小于 $0$。然后是 Ollie，对刚才得到的数，和 $M,N$ 中较小的那个数，再进行同样的操作……直到一个人得到了 $0$，他就取得了胜利。下面是他们用 $(25,7)$ 两个数游戏的过程：
Start:$(25,7)$
Stan:$(11,7)$
Ollie:$(4,7)$
Stan:$(4,3)$
Ollie:(1,3)$
Stan:$(1,0)$
Stan 赢得了游戏的胜利。
现在，假设他们完美地操作，谁会取得胜利呢？
### 输入格式
**本题有多组测试数据。**
第一行为测试数据的组数 $C$。
下面 $C$ 行，每行为一组数据，包含两个正整数 $M,N(M,N<2^{31})$。
**输出格式**
对每组输入数据输出一行，如果 Stan 胜利，则输出 `Stan wins`；否则输出 `Ollie wins`。by cmll02 @ 2020-01-23 10:27:17
类型：题面修改
题目：P2341 【模板】强连通分量 / [HAOI2006]受欢迎的牛
新题面：
### 题目背景
本题测试数据已修复。
### 题目描述
每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 $A$ 喜欢 $B$，$B$ 喜欢 $C$，那么 $A$ 也喜欢 $C$。牛栏里共有 $N$ 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。
### 输入格式
第一行：两个用空格分开的整数：$N$ 和 $M$。
接下来 $M$ 行：每行两个用空格分开的整数：$A$ 和 $B$，表示 $A$ 喜欢 $B$。
### 输出格式
一行单独一个整数，表示明星奶牛的数量。
### 说明/提示
只有 $3$ 号奶牛可以做明星。
【数据范围】
对于 $10\%$ 的数据，$N\le20, M\le50$。
对于 $30\%$的数据,$N\le1000,M\le20000$。
对于 $70\%$的数据,$N\le5000,M\le50000$。
对于 $100\%$的数据,$N\le10000,M\le50000$。by cmll02 @ 2020-01-23 10:29:47
类型：题面修改
题目：P1296 奶牛的耳语
新题面：
### 题目描述
在你的养牛场，所有的奶牛都养在一排呈直线的牛栏中。一共有 $n$ 头奶牛，其中第 $i$ 头牛在直线上所处的位置可以用一个整数坐标 $p_i(0\le p_i \le 10^8)$ 来表示。在无聊的日子里，奶牛们常常在自己的牛栏里与其它奶牛交流一些八卦新闻。每头奶牛发出的声音响度是一样的，而由于声波的能量衰减，某头奶牛发出的声音只能被与它距离不超过 $d(0 \le d \le 10^4)$ 的奶牛所听到，这样这对奶牛就称为可以相互交流的。现在给出所有奶牛的位置和声音所能传播的最远距离 $d$ ，请你编个程序来计算你的养牛场里究竟有多少对可以相互交流的奶牛。
### 输入格式
第一行包含两个整数 $n,d$。
第二行包含 $n$ 个整数，每个整数都是一个坐标 $p_i$，描述一头奶牛在直线上的位置。
### 输出格式
一个数，表示养牛场中可以相互交流奶牛的对数。
### 说明/提示
数据规模
对于 $40\%$ 的数据，$n\le10^3$。
对于 $100\%$ 的数据，$n\le 10^6$。by cmll02 @ 2020-01-23 10:31:36
类型：题面修改
题目：P2197 【模板】nim游戏
新题面：
### 题目描述
甲，乙两个人玩 Nim 取石子游戏。
Nim 游戏的规则是这样的：地上有 $n$ 堆石子（每堆石子数量小于 $10000$），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这 $n$ 堆石子的数量，他想知道是否存在先手必胜的策略。
### 输入格式
**本题有多组测试数据。**
第一行一个整数 $T(T\le10)$，表示有 $T$ 组数据
接下来每两行是一组数据，第一行一个整数 $n$，表示有 $n$ 堆石子，$n\le10000$。
第二行有 $n$ 个数，表示每一堆石子的数量.
### 输出格式
共 $T$ 行，如果对于这组数据存在先手必胜策略则输出 `Yes`,否则输出 `No`，每个单词一行。by zhouwc @ 2020-01-23 11:04:20
13页 @LCuter 3172，3312 已经修改。感谢贡献
by zhouwc @ 2020-01-23 11:08:01
@shygo_cmll02 4道题均已修改，感谢贡献
by cmll02 @ 2020-01-23 12:04:07
抱歉P1290漏了一个$麻烦管理员大大补上。。
by feecle6418 @ 2020-01-23 12:57:15
类型：试题提供
题目：[ICPC2016 China Final] Mr.Panda and TubeMaster