#P18453. Computational Complexity
Computational Complexity
Computational Complexity
题目描述
Ham 在算法课上学习了计算复杂度。用 表示算法处理规模为 的输入所需的时间。例如,归并排序满足递推关系
$$T(n)=2T\left(\left\lfloor\frac n2\right\rfloor\right)+O(n),$$由此可以得到上界 。
Ham 喜欢学习和探索,决定研究更困难的情形。有两个互相调用的算法 和 :
- 调用 、、 和 。
- 调用 、、 和 。
他想知道两个算法精确需要多少次操作。本题形式化定义如下。
给定 与 ,对于所有整数 ,定义
$$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).$$其中 分别表示两个算法的操作次数。给定若干个查询参数 ,求 和 对 取模的结果。
表示不大于 的最大整数。例如 ,,,,,。
输入格式
第一行包含四个整数 ,满足
接下来 行,每行包含一个整数 ,满足 ,表示一次查询。
注意 是同一组初始值和模数下的查询数量,不是外层测试数据组数。 与 独立给定; 不保证为质数。 合法,此时没有查询输出。
输出格式
输出 行。每行包含两个整数,依次为对应查询的 与 ,用一个空格分隔。
原样例 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