#P3788. ZL密码锁

    ID: 2993 传统题 2000ms 128MiB 尝试: 6 已通过: 5 难度: 6 上传者: 标签>CF2100提高欧几里得算法同余的加减乘运算秦九韶算法二次剩余快速幂递推

ZL密码锁

题目描述

话说考古学家 ZL 走进了一个山洞……

ZL 在山洞深处发现了一组密码锁,并断定这里藏着数不清的宝藏。经过一番寻找,ZL 发现该密码锁上写着一串阿拉伯数字,看起来这些数字中有着一些微妙的联系。于是他动用了 120120 分脑细胞,凭着藐视一切 IMO 选手的强大逻辑推理能力,找到了规律,并破解了几个密码锁。

可 ZL 毕竟是人,他也是会累的呀 T_T。

况且他的 GPS 显示前方还有成百上千个密码锁!!!!

于是他把问题简化了一下,求助于身为 OI 神犇的你。

数列 ana_n 由如下关系式定义:

  1. a[0]=0a[0]=0;
  2. a[n]=f(a[n−1])a[n]=f(a[n-1])。

其中 f(x)f(x) 是一个正整数系数的 mm 次多项式。

对任意给定的 xx 和 yy,求 axa_x 和 aya_y 的最大公约数 dd。

令 ss 为 dd 模 xx 的余数,tt 为 dd 模 yy 的余数。

给定 rr 和一个奇质数 pp,保证 rr 不是 pp 的整数倍。

废话完毕,现在我们的问题是:

求方程 (rx2+sx+t) mod p=0(rx^2+sx+t) \bmod p=0 有几个模 pp 意义下的正整数解。

对每个函数 y=f(x)y=f(x) 将进行 TT 次询问。

输入格式

输入文件包括 T+3T+3 行。

第一行一个正整数 mm。

第二行 m+1m+1 个正整数 cm…c0c_m \dots c_0,其中ci (m≥i≥0)c_i~(m \ge i \ge 0) 表示 f(x)f(x) 中 xix_i 的系数。

第三行一个正整数 TT,表示询问次数。

以下 TT 行每行四个正整数,分别表示 x,y,r,px,y,r,p。

输出格式

输出文件包含 TT 行,每行仅输出一个整数表示方程有多少组解(模 pp 的意义下)。

1
2 1
1
4 8 7 3
0

数据规模与约定

对于 100%100\% 的数据,T≤103T \le 10^3,m≤10m \le 10,x<yx<y,x≤105x \le 10^5,y≤108y \le 10^8,p≤108p \le 10^8。