#P10154. 「FAOI-R3」移民计划 (C)
「FAOI-R3」移民计划 (C)
题目背景
提示:题目描述最后附有一份简洁题意。
题外话:CCF 的 F 是 Federation,不是 Foundation。
年 月 日,为了响应国家号召,促进区域 OI 水平均衡发展,时任 GZCF(Guizhou Computer Federation,贵州省计算机协会)主任 strcmp(下称「小 W」) 和时任 CQCF(Chongqing Computer Federation,重庆市计算机协会)主任 CQYC_ZJYjoe(下称「小 Z」) 达成秘密协议:从重庆市抽调一批 OIers 移民到贵州省,路费等由小 Z 承担,但小 W 需要安排好 TA 们的住所。
题目描述
根据小 Z 的要求,小 W 一共要盖 座楼房。为了更符合重庆人的品味(?),这些楼房需要「错落有致」:具体来说,第 座楼房的层高应为 米,且楼高 米单调不降(即 )。当然,每座楼房的楼层数 应为正整数。
与此同时,小 W 已经找到了一座层高为 ,楼层数 的烂尾楼(),并决定将它作为第 座楼房。
为了避免小 Z 反悔,小 W 决定尽快完工,因此他这么盖楼:
- 在所有使得 的 中,取最小值作为 ,即 ;
- 在所有使得 的 中,取最小值作为 ,即 ;
- 在所有使得 的 中,取最小值作为 ,即 ;
- ……
- 在所有使得 的 中,取最小值作为 ,即 ;
- ……
- 在所有使得 的 中,取最小值作为 ,即 。
当然,小 W 最关注的并不是这个,而是另外一件事情——他前一天成功忽悠了 CCF 主席,双方达成协议:CCF 补贴给小 W 元钱。
他想知道:此时 CCF 会补贴给他多少元钱?答案对 取模。
给定两个正整数 。
现有两个正整数数列 和一个正整数 ,满足:
$$\begin{cases} s_1=a, \\ s_i=\lceil \dfrac{h_{i-1}}{i} \rceil, \\ h_i=i \times s_i,\\ W=h_1\times h_2\times \ldots\times h_n. \end{cases} $$试计算 的值。答案对 取模。
输入格式
本题有多组数据。
第一行,一个正整数 ,表示数据组数。
下面 行,每行两个整数 。
输出格式
行,每行一个整数,对应一组数据的答案。
7
1 1
2 4
3 9
10 6
23 44
108 301
9181918 918918
1
16
1080
721510288
57314155
568048964
118153594
提示
样例解释:
- 对于第 组数据, 数列为 , 数列为 ,故答案为 。
- 对于第 组数据, 数列为 , 数列为 ,故答案为 。
- 对于第 组数据, 数列为 , 数列为 ,故答案为 。
- 对于第 组数据,取模前的答案为 。
测试点编号 | 分值 | ||
---|---|---|---|
对于 的数据,,,。