#P18453. Computational Complexity

Computational Complexity

Computational Complexity

题目描述

Ham 在算法课上学习了计算复杂度。用 T(n)T(n) 表示算法处理规模为 nn 的输入所需的时间。例如,归并排序满足递推关系

$$T(n)=2T\left(\left\lfloor\frac n2\right\rfloor\right)+O(n),$$

由此可以得到上界 T(n)=O(nlog⁡n)T(n)=O(n\log n)。

Ham 喜欢学习和探索,决定研究更困难的情形。有两个互相调用的算法 A1(n)A_1(n) 和 A2(n)A_2(n):

  • A1(n)A_1(n) 调用 A2(⌊n/2⌋)A_2(\lfloor n/2\rfloor)、A2(⌊n/3⌋)A_2(\lfloor n/3\rfloor)、A2(⌊n/5⌋)A_2(\lfloor n/5\rfloor) 和 A2(⌊n/7⌋)A_2(\lfloor n/7\rfloor)。
  • A2(n)A_2(n) 调用 A1(⌊n/2⌋)A_1(\lfloor n/2\rfloor)、A1(⌊n/3⌋)A_1(\lfloor n/3\rfloor)、A1(⌊n/4⌋)A_1(\lfloor n/4\rfloor) 和 A1(⌊n/5⌋)A_1(\lfloor n/5\rfloor)。

他想知道两个算法精确需要多少次操作。本题形式化定义如下。

给定 f(0)f(0) 与 g(0)g(0),对于所有整数 n≥1n\ge1,定义

$$f(n)=\max\left(n, g\left(\left\lfloor\frac n2\right\rfloor\right)+ g\left(\left\lfloor\frac n3\right\rfloor\right)+ g\left(\left\lfloor\frac n5\right\rfloor\right)+ g\left(\left\lfloor\frac n7\right\rfloor\right)\right),$$$$g(n)=\max\left(n, f\left(\left\lfloor\frac n2\right\rfloor\right)+ f\left(\left\lfloor\frac n3\right\rfloor\right)+ f\left(\left\lfloor\frac n4\right\rfloor\right)+ f\left(\left\lfloor\frac n5\right\rfloor\right)\right).$$

其中 f(n),g(n)f(n),g(n) 分别表示两个算法的操作次数。给定若干个查询参数 mm,求 f(m)f(m) 和 g(m)g(m) 对 MM 取模的结果。

⌊x⌋\lfloor x\rfloor 表示不大于 xx 的最大整数。例如 ⌊0.5⌋=0\lfloor0.5\rfloor=0,⌊11.3⌋=11\lfloor11.3\rfloor=11,⌊101.9⌋=101\lfloor101.9\rfloor=101,⌊99⌋=99\lfloor99\rfloor=99,⌊0⌋=0\lfloor0\rfloor=0,⌊2⌋=2\lfloor2\rfloor=2。

输入格式

第一行包含四个整数 f(0),g(0),T,Mf(0),g(0),T,M,满足

0≤f(0),g(0),T≤105,2≤M≤1015.0\le f(0),g(0),T\le10^5,\qquad2\le M\le10^{15}.

接下来 TT 行,每行包含一个整数 mm,满足 0≤m≤10150\le m\le10^{15},表示一次查询。

注意 TT 是同一组初始值和模数下的查询数量,不是外层测试数据组数。f(0)f(0) 与 g(0)g(0) 独立给定;MM 不保证为质数。T=0T=0 合法,此时没有查询输出。

输出格式

输出 TT 行。每行包含两个整数,依次为对应查询的 f(m) mod Mf(m)\bmod M 与 g(m) mod Mg(m)\bmod M,用一个空格分隔。

原样例 1

1958 920 10 100000000000
0
1
2
3
10
100
200
1000
19580920
20232023
1958 920
3680 7832
10592 9554
17504 11276
50294 64826
784112 893714
1894550 1905470
12057866 12979424
71481494756 48626708512
28127864908 7251681354

原样例 2

0 0 10 100000000000
0
1
2
3
4
10
20
30
40
100
0 0
1 1
2 2
3 3
4 4
11 12
25 26
41 41
55 58
162 172