#H1025. 「MCOI-07」Dream and Machine Learning

「MCOI-07」Dream and Machine Learning

题目描述

Dream 构造了一个红石计算机来验证 ber(modm)b^e\equiv r\pmod m 形式的公式。
Dream 固定了 bbmm 并且构造了 nn 对满足以上条件的 (e,r)(e,r) 正整数对。
可惜,Dream 忘记了 mm 的具体值。现在他给了你 bb 和这 nn 对数。请替代 Dream 的计算机,回答 qqbai(modm)b^{a_i}\pmod m 形式的询问。

输入格式

第一行三个正整数,分别代表 bbnn,和 qq
接下来 nn 行,每行两个正整数,分别代表一对 eerr
接下来 qq 行,每行一个正整数,代表一个 aia_i

输出格式

输出 qq 行,对应询问的答案。

3 8 3
108 75
616 36
220 16
37 66
114 64
514 24
1919 65
810 33
19260817
123456789
23333333
3
79
49
请见附件 sample.in
请见附件 sample.out

说明/提示

样例 1 解释

可以唯一确定 m=97m=97
样例 1 仅仅说明题意,并不代表任何 subtask 的任何测试点。

数据规模与约定

本题采用捆绑测试。

  • Subtask 1(5 pts):m103m\le10^3
  • Subtask 2(19 pts):m109m\le10^9
  • Subtask 3(19 pts):m1019m\le10^{19}
  • Subtask 4(19 pts):m1029m\le10^{29}
  • Subtask 5(19 pts):m1099m\le10^{99}
  • Subtask 6(19 pts):m10199m\le10^{199}

对于 100%100\% 的数据,b{2,3}b\in\{2,3\}1q1001\le q\le1002e,ai1092\le e,a_i\le 10^9n=105n=10^5
保证 mm 为质数。
保证 所有 ee 互不相同。
保证 数据随机。