#P9552. 「CROI · R1」浣熊的小溪
「CROI · R1」浣熊的小溪
题目背景
“从太阳里奔来,又迎着阳光走去;张开熊爪,与风相拥,离别之际,却低首自吟。” 那梦枫畔嬉戏的成长,那阳光下不羁的信仰,历久弥坚,在无数浣熊的心畔回响。 可叹,灵溪上畔,一人意志,大小工事,割裂了纯真的年华,刀刻了落寞的隔阂。 那明澈的小溪,那快乐的往日,还会,在感怀中驻足吗……
题目描述
浣熊岭的森林可以看作一张 的网格图。工厂排放的废水污染了纵贯森林的梦枫溪(一条直线),导致所经区域对浣熊是有害的。小浣熊 CleverRaccoon 为了研究废水对浣熊的危害,要寻求你的帮助。
设 表示一条直线最多能穿过 的网格图的格子数。
小浣熊有两种问题想要问你:
- 给定 ,求 ;
- 给定 ,你需要找到 ,满足 ,且 尽可能小。求 的最小值对 取模的结果。数据保证 。
输入格式
本题包含多组测试数据。
第一行,输入一个正整数 ,表示有 次询问。
对于每次询问:
第一行,输入一个正整数 ,表示问题类型。
第二行,若 ,输入 个正整数 和 ;若 ,输入 个正整数 、 和 。
输出格式
共 行,对于每次询问:一行输出 个正整数,表示对应问题的答案。
样例 #1
样例输入 #1
2
1
2 3
2
2 3 10
样例输出 #1
4
12
提示
样例解释 #1
对于第一次询问:
下图所示的情况是一种最佳构造方案,梦枫溪穿过 的网格森林时,最多穿过 个小网格(黄色部分为穿过的网格,灰色部分为未穿过的网格)。
下示方案不是一种最佳方案,梦枫溪是从两个绿色网格中间的一个顶点上穿过的,所以两个绿色区域都没有被穿过。因此梦枫溪只穿过了 个小网格。
对于第二次询问:
如下图所示,当 , 时,才能使梦枫溪穿过 个网格的情况下,在原基础添加的 个网格是最少的(红色虚线左边是原来的森林,右边是添加的部分)。
数据范围
对于 的数据,保证 ,,,。