今天天我们来讲“函数”
不完美的分割线
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一、一次函数（LINEAR FUNCTION）
1. 定义与解析式
* 一般式：y=kx+by = kx + by=kx+b （k,bk, bk,b 为常数，且 k≠0k \neq 0k=0）
* 特例：当 b=0b=0b=0 时，y=kxy=kxy=kx 为正比例函数。
* 关键：kkk 是斜率，bbb 是截距。
2. 图像特征
* 形状：直线
* 画法：两点确定一条直线
3. 性质速查表
系数 图像走势 增减性 k > 0 上升 单调递增 k < 0 下降 单调递减
4. 待定系数法
设 y=kx+by=kx+by=kx+b，代入两点坐标解方程组。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、二次函数（QUADRATIC FUNCTION）
1. 定义与解析式
* 一般式：y=ax2+bx+cy = ax^2 + bx + cy=ax2+bx+c （a≠0a \neq 0a=0）
* 顶点式：y=a(x−h)2+ky = a(x - h)^2 + ky=a(x−h)2+k （顶点 (h,k)(h, k)(h,k)）
* 交点式：y=a(x−x1)(x−x2)y = a(x - x_1)(x - x_2)y=a(x−x1 )(x−x2 ) （与x轴交点 x1,x2x_1, x_2x1 ,x2 ）
2. 图像特征
* 形状：抛物线
* 开口：a>0a > 0a>0 向上，a<0a < 0a<0 向下
* 对称轴：x=−b2ax = -\frac{b}{2a}x=−2ab
* 顶点：(−b2a,4ac−b24a)\left( -\frac{b}{2a}, \frac{4ac - b^2}{4a} \right)(−2ab ,4a4ac−b2 )
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、例题详解（3种题型）
例题1：一次函数解析式的确定
题目：已知一次函数图像经过点 A(1,3)A(1, 3)A(1,3) 和 B(−2,−3)B(-2, -3)B(−2,−3)，求函数解析式。
解答：
1. 设解析式为：y=kx+by = kx + by=kx+b
2. 将两点代入：
{3=k×1+b−3=k×(−2)+b\begin{cases} 3 = k \times 1 + b \\ -3 = k \times (-2) + b \end{cases} {3=k×1+b−3=k×(−2)+b
3. 解方程组：
* 上减下：3−(−3)=k−(−2k)3 - (-3) = k - (-2k)3−(−3)=k−(−2k) → 6=3k6 = 3k6=3k → k=2k = 2k=2
* 代入：3=2×1+b3 = 2 \times 1 + b3=2×1+b → b=1b = 1b=1
4. 解析式为：y=2x+1y = 2x + 1y=2x+1
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
例题2：二次函数最值问题
题目：用长为24米的篱笆围一个矩形菜地，一面靠墙。问长宽各多少时面积最大？最大面积是多少？
解答：
1. 建模：设与墙垂直的边长为 xxx 米，则与墙平行的边为 (24−2x)(24-2x)(24−2x) 米
2. 列式：面积 S=x(24−2x)=−2x2+24xS = x(24-2x) = -2x^2 + 24xS=x(24−2x)=−2x2+24x
3. 分析：a=−2<0a = -2 < 0a=−2<0，开口向下，有最大值
4. 求顶点（最值点）：
* 顶点横坐标：x=−b2a=−242×(−2)=6x = -\frac{b}{2a} = -\frac{24}{2 \times (-2)} = 6x=−2ab =−2×(−2)24 =6
* 最大面积：Smax=−2×62+24×6=−72+144=72S_{max} = -2 \times 6^2 + 24 \times 6 = -72 + 144 = 72Smax =−2×62+24×6=−72+144=72
5. 答：当宽为6米，长为12米时，面积最大为72平方米。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
例题3：一次函数与二次函数的综合应用
题目：某商品进价40元，售价60元时每天可卖100件。调查发现：每降价1元可多卖10件，每涨价1元则少卖10件。设售价为 xxx 元，日利润为 yyy 元。
(1) 求 yyy 关于 xxx 的函数关系式
(2) 售价定为多少时，日利润最大？最大利润是多少？
解答：
(1) 分情况建立函数：
* 当 x≤60x \leq 60x≤60 时（降价）：
销售量：100+10(60−x)=700−10x100 + 10(60 - x) = 700 - 10x100+10(60−x)=700−10x
单件利润：x−40x - 40x−40
∴ y=(x−40)(700−10x)=−10x2+1100x−28000y = (x-40)(700-10x) = -10x^2 + 1100x - 28000y=(x−40)(700−10x)=−10x2+1100x−28000
* 当 x≥60x \geq 60x≥60 时（涨价）：
销售量：100−10(x−60)=700−10x100 - 10(x-60) = 700 - 10x100−10(x−60)=700−10x（巧合，表达式相同）
单件利润：x−40x - 40x−40
∴ y=(x−40)(700−10x)=−10x2+1100x−28000y = (x-40)(700-10x) = -10x^2 + 1100x - 28000y=(x−40)(700−10x)=−10x2+1100x−28000
* 注意：实际中降价和涨价的表达式通常不同，但本题数字设计导致一致。
(2) 求最值：
y=−10x2+1100x−28000y = -10x^2 + 1100x - 28000y=−10x2+1100x−28000
* 化为顶点式：y=−10(x−55)2+2250y = -10(x-55)^2 + 2250y=−10(x−55)2+2250
* 当 x=55x = 55x=55 时，ymax=2250y_{max} = 2250ymax =2250
* 验证合理性：x=55<60x=55<60x=55<60，属于降价销售，符合模型
* 答：定价55元时利润最大，最大利润2250元。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、解题思路总结
题型 关键步骤 注意事项 求解析式 1. 设解析式<br>2. 代点列方程<br>3. 求解系数 一次函数用两点，二次函数用三点或顶点信息 最值问题 1. 建立函数模型<br>2. 化为顶点式<br>3. 结合定义域验证 注意自变量实际取值范围对最值的影响 综合应用 1. 分段分析<br>2. 分别建模<br>3. 全局比较 注意条件转换，明确变量实际意义
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、易错提醒
1. 忘记 k≠0k \neq 0k=0, a≠0a \neq 0a=0 的前提条件
2. 二次函数配方错误：y=ax2+bx+c=a(x+b2a)2+4ac−b24ay=ax^2+bx+c = a(x+\frac{b}{2a})^2 + \frac{4ac-b^2}{4a}y=ax2+bx+c=a(x+2ab )2+4a4ac−b2
3. 实际应用题忽略定义域：边长、售价、件数等必须为正整数或有范围限制
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
下面我们来看几道例题
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目描述
给定 nnn 个一次函数 fi(x)=aix+bif_i(x) = a_ix + b_ifi (x)=ai x+bi ，其中 xxx 为形式幂级数的占位符。
从这 nnn 个中选出 kkk 个 gi(x)g_i(x)gi (x) （1≤i≤k1\leq i \leq k1≤i≤k），定义集合 HHH 为 gig_igi 的若干次幂的乘积模 x2x^2x2 的值所构成的集合。即：
H={∏i=1kgi(x)j mod x2|0≤a,b<p}H=\left\{\prod_{i=1}^k g_i(x)^j\bmod x^2\middle|0 \leq a, b < p \right\} H={i=1∏k gi (x)jmodx2 0≤a,b<p}
其中 jjj 是任意非负整数且对于每个 iii 可以有不同的 jjj。
需要注意的是，0⋅x+10\cdot x+10⋅x+1 始终在集合 HHH 中（而非 0⋅x+00 \cdot x + 00⋅x+0），即使 k=0k = 0k=0 也是如此。
给定 A,BA, BA,B，求出所有满足 Ax+B∈HAx+B\in HAx+B∈H 的集合 HHH 的 kkk 的最小值。
若不存在 HHH 使得 Ax+B∈HAx+B\in HAx+B∈H，输出 -1。
所有运算均在模 ppp 意义下进行。
输入格式
第一行四个整数 n,p,A,Bn, p, A, Bn,p,A,B。
接下来 nnn 行，每行两个整数 ai,bia_i, b_iai ,bi 。
输出格式
第一行一个整数 kkk，表示答案。
若存在方案，接下来 kkk 行，每行两个整数 a,ba, ba,b，需满足
(∏fa(x)b) mod x2=Ax+B\left(\prod f_a(x)^b\right)\bmod x^2=Ax + B (∏fa (x)b)modx2=Ax+B
aaa 的顺序可任意。
输入输出样例 #1
输入 #1
输出 #1
输入输出样例 #2
输入 #2
输出 #2
输入输出样例 #3
输入 #3
输出 #3
说明/提示
另有两组大样例与 checker，下载地址见附件。
要测试你某个测试点的答案，你需要在你本题目录下的命令行中执行：
<checker> <input‐file> <output‐file> <answer‐file> [<report‐file>]
其中：
* <checker> 表示校验器可执行文件；
* <input‐file> 表示该测试点的输入文件，如 func1.in；
* <output‐file> 表示该测试点你的答案，如 func1.out；
* <answer‐file> 表示该测试点的答案文件（只需要提供输出的第一行），如 func1.ans；
* <report‐file> 为可选参数，如果没有给定该参数，校验器将输出至终端；否则将输出至该文件，如 report1.txt。
对于所有数据，2≤p≤1092\leq p\leq 10^92≤p≤109，保证 ppp 为质数，1≤n≤5×1031\leq n \leq 5 \times 10^31≤n≤5×103，0≤ai,A<p0\leq a_i, A < p0≤ai ,A<p，1≤bi,B<p1\leq b_i, B < p1≤bi ,B<p。
详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：
子任务编号 分值 nnn ppp 特殊性质 111 555 =1=1=1 ≤1000\leq 1000≤1000 222 555 ≤3\leq 3≤3 =7=7=7 333 151515 ≤100\leq 100≤100 =31=31=31 444 202020 A=B=1A=B=1A=B=1 555 252525 ≤20\leq 20≤20 666 151515 ≤500\leq 500≤500 777 151515
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 题意与问题转化
我们有 nnn 个一次函数：
fi(x)=aix+bi,ai,bi∈Fp, bi≠0f_i(x) = a_i x + b_i, \quad a_i,b_i \in \mathbb{F}_p,\ b_i\neq 0 fi (x)=ai x+bi ,ai ,bi ∈Fp , bi =0
在模 ppp 意义下运算，ppp 为质数。
定义集合 HHH：
* 从这 nnn 个函数中选出 kkk 个 g1,…,gkg_1,\dots,g_kg1 ,…,gk （可重复选）
* 对每个 gig_igi 选取幂指数 ei∈{0,1,…,p−1}e_i \in \{0,1,\dots,p-1\}ei ∈{0,1,…,p−1}
* 计算 ∏i=1kgi(x)ei mod x2\prod_{i=1}^k g_i(x)^{e_i} \bmod x^2∏i=1k gi (x)ei modx2，即保留常数项和一次项
* 所有这样的结果构成 HHH
题目要求：给定 A,BA,BA,B，求最小的 kkk 使得存在某个 HHH 满足 Ax+B∈HAx+B \in HAx+B∈H。若不存在输出 −1-1−1。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 代数结构分析
记一次函数 g(x)=b+axg(x) = b + a xg(x)=b+ax 为二元组 (b,a)(b,a)(b,a)，其中 b∈Fp∗b \in \mathbb{F}_p^*b∈Fp∗ , a∈Fpa \in \mathbb{F}_pa∈Fp 。
乘法（模 x2x^2x2 截断）：
(b1,a1)⋅(b2,a2)=(b1b2, a1b2+a2b1)(b_1,a_1) \cdot (b_2,a_2) = (b_1 b_2,\ a_1 b_2 + a_2 b_1) (b1 ,a1 )⋅(b2 ,a2 )=(b1 b2 , a1 b2 +a2 b1 )
单位元 e=(1,0)e = (1,0)e=(1,0)。
幂运算公式（可通过归纳法证明）：
(b,a)m=(bm, mbm−1a)(b,a)^m = (b^m,\ m b^{m-1} a) (b,a)m=(bm, mbm−1a)
对任意整数 m≥0m \ge 0m≥0 成立。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 对数同构化简
令 c=ab−1(modp)c = a b^{-1} \pmod{p}c=ab−1(modp)，则 (b,a)=(b,bc)(b,a) = (b, bc)(b,a)=(b,bc)。
乘法规则变为：
(b1,b1c1)⋅(b2,b2c2)=(b1b2, b1b2(c1+c2))(b_1,b_1 c_1) \cdot (b_2,b_2 c_2) = (b_1 b_2,\ b_1 b_2 (c_1 + c_2)) (b1 ,b1 c1 )⋅(b2 ,b2 c2 )=(b1 b2 , b1 b2 (c1 +c2 ))
即
(b1,c1)⋅(b2,c2)=(b1b2, c1+c2)(b_1, c_1) \cdot (b_2, c_2) = (b_1 b_2,\ c_1 + c_2) (b1 ,c1 )⋅(b2 ,c2 )=(b1 b2 , c1 +c2 )
其中这里的 (b,c)(b,c)(b,c) 表示函数 b(1+cx)b(1 + c x)b(1+cx)。
因此有群同构：
φ:G→Fp∗×Fp,(b,a)↦(b, ab−1)\varphi: G \to \mathbb{F}_p^* \times \mathbb{F}_p,\quad (b,a) \mapsto (b,\ a b^{-1}) φ:G→Fp∗ ×Fp ,(b,a)↦(b, ab−1)
逆映射为 (β,γ)↦(β,βγ)(\beta, \gamma) \mapsto (\beta, \beta\gamma)(β,γ)↦(β,βγ)。
在新坐标下乘法简单：
(β1,γ1)∗(β2,γ2)=(β1β2, γ1+γ2)(\beta_1, \gamma_1) * (\beta_2, \gamma_2) = (\beta_1 \beta_2,\ \gamma_1 + \gamma_2) (β1 ,γ1 )∗(β2 ,γ2 )=(β1 β2 , γ1 +γ2 )
幂运算：
(β,γ)m=(βm, mγ)(\beta, \gamma)^m = (\beta^m,\ m \gamma) (β,γ)m=(βm, mγ)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 问题重写
设目标函数 Ax+BAx+BAx+B 对应 (B,A)(B,A)(B,A)，在同构下映射为：
(B,AB−1)=(B,C)(B, A B^{-1}) = (B, C) (B,AB−1)=(B,C)
其中 C=AB−1(modp)C = A B^{-1} \pmod{p}C=AB−1(modp)。
给定 nnn 个函数 fi=(bi,ai)f_i = (b_i, a_i)fi =(bi ,ai )，对应 (βi,γi)=(bi,aibi−1)(\beta_i, \gamma_i) = (b_i, a_i b_i^{-1})(βi ,γi )=(bi ,ai bi−1 )。
对于选出的 kkk 个 (βi,γi)(\beta_i, \gamma_i)(βi ,γi ) 和指数 ei∈{0,1,…,p−1}e_i \in \{0,1,\dots,p-1\}ei ∈{0,1,…,p−1}，乘积为：
∏j=1k(βj,γj)ej=(∏j=1kβjej, ∑j=1kejγj)\prod_{j=1}^k (\beta_j, \gamma_j)^{e_j} = \left( \prod_{j=1}^k \beta_j^{e_j},\ \sum_{j=1}^k e_j \gamma_j \right) j=1∏k (βj ,γj )ej =(j=1∏k βjej , j=1∑k ej γj )
要求等于 (B,C)(B, C)(B,C)，即：
∏j=1kβjej≡B(modp)(1)\prod_{j=1}^k \beta_j^{e_j} \equiv B \pmod{p} \tag{1} j=1∏k βjej ≡B(modp)(1)
∑j=1kejγj≡C(modp)(2)\sum_{j=1}^k e_j \gamma_j \equiv C \pmod{p} \tag{2} j=1∑k ej γj ≡C(modp)(2)
其中 βj=bj∈Fp∗\beta_j = b_j \in \mathbb{F}_p^*βj =bj ∈Fp∗ ，γj=ajbj−1∈Fp\gamma_j = a_j b_j^{-1} \in \mathbb{F}_pγj =aj bj−1 ∈Fp 。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 取离散对数
设 ggg 是模 ppp 的原根，记 βj=guj, B=gu\beta_j = g^{u_j},\ B = g^{u}βj =guj , B=gu，则方程 (1) 变为：
∑j=1kejuj≡u(modp−1)(1’)\sum_{j=1}^k e_j u_j \equiv u \pmod{p-1} \tag{1'} j=1∑k ej uj ≡u(modp−1)(1’)
方程 (2) 不变：
∑j=1kejγj≡C(modp)(2)\sum_{j=1}^k e_j \gamma_j \equiv C \pmod{p} \tag{2} j=1∑k ej γj ≡C(modp)(2)
其中 ej∈{0,1,…,p−1}e_j \in \{0,1,\dots,p-1\}ej ∈{0,1,…,p−1}。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 问题转化为向量覆盖
记 m1=p−1m_1 = p-1m1 =p−1, m2=pm_2 = pm2 =p，它们互质。
对每个给定的函数 fif_ifi ，定义向量：
vi=(ui,γi)∈Zm1×Zm2\mathbf{v}_i = (u_i, \gamma_i) \in \mathbb{Z}_{m_1} \times \mathbb{Z}_{m_2} vi =(ui ,γi )∈Zm1 ×Zm2
目标向量：
t=(u,C)∈Zm1×Zm2\mathbf{t} = (u, C) \in \mathbb{Z}_{m_1} \times \mathbb{Z}_{m_2} t=(u,C)∈Zm1 ×Zm2
问题变为：选择 kkk 个向量 vi1,…,vik\mathbf{v}_{i_1}, \dots, \mathbf{v}_{i_k}vi1 ,…,vik （可重复）和非负系数 e1,…,ek∈{0,…,p−1}e_1,\dots,e_k \in \{0,\dots,p-1\}e1 ,…,ek ∈{0,…,p−1}，使得
∑j=1kejvij≡t(mod (m1,m2))\sum_{j=1}^k e_j \mathbf{v}_{i_j} \equiv \mathbf{t} \quad (\text{mod } (m_1, m_2)) j=1∑k ej vij ≡t(mod (m1 ,m2 ))
这里模 (m1,m2)(m_1, m_2)(m1 ,m2 ) 表示第一个分量模 m1m_1m1 ，第二个分量模 m2m_2m2 。
最小化 kkk。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7. 最小 K 的可能值分析
7.1 可行性判定
设 S={vi}S = \{\mathbf{v}_i\}S={vi } 是给定的 nnn 个向量。
记 LLL 为 SSS 中所有向量在 Zm1×Zm2\mathbb{Z}_{m_1} \times \mathbb{Z}_{m_2}Zm1 ×Zm2 中生成的子群（系数取任意整数）。
记 LpL_pLp 为系数限制在 {0,1,…,p−1}\{0,1,\dots,p-1\}{0,1,…,p−1} 时能生成的集合。
关键观察：因为 eje_jej 可取 000 到 p−1p-1p−1 任意整数，并且 ppp 是质数，所以对任意整数系数组合 ∑cjvj\sum c_j \mathbf{v}_j∑cj vj ，我们可以通过给某些系数加 ppp 的倍数将其调整到 [0,p−1][0,p-1][0,p−1] 范围内，只要 kkk 足够大。
更准确地说，如果目标 t\mathbf{t}t 属于 LLL，则存在整数 djd_jdj 使得：
t=∑j=1ndjvj\mathbf{t} = \sum_{j=1}^n d_j \mathbf{v}_j t=j=1∑n dj vj
我们可对每个 djd_jdj 模 ppp 得到 ej∈{0,…,p−1}e_j \in \{0,\dots,p-1\}ej ∈{0,…,p−1}，但这样会改变第一个分量的值（模 m1m_1m1 下）。因为 ppp 和 m1=p−1m_1 = p-1m1 =p−1 互质，通过调整 kkk（即向量的选择）可以纠正。
结论：t\mathbf{t}t 能被生成的充要条件是 t∈L\mathbf{t} \in Lt∈L，即 t\mathbf{t}t 属于 SSS 生成的子群。
若 t∉L\mathbf{t} \notin Lt∈/L，则无解，输出 −1-1−1。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7.2 判断是否属于子群
设 M1=m1=p−1M_1 = m_1 = p-1M1 =m1 =p−1, M2=m2=pM_2 = m_2 = pM2 =m2 =p。
考虑扩展向量 wi=(ui,γi,1)∈ZM1×ZM2×Z\mathbf{w}_i = (u_i, \gamma_i, 1) \in \mathbb{Z}_{M_1} \times \mathbb{Z}_{M_2} \times \mathbb{Z}wi =(ui ,γi ,1)∈ZM1 ×ZM2 ×Z，实际上我们需要判断是否存在整数 xjx_jxj 使得：
∑xjuj≡u (mod M1)\sum x_j u_j \equiv u \ (\text{mod }M_1) ∑xj uj ≡u (mod M1 )
∑xjγj≡C (mod M2)\sum x_j \gamma_j \equiv C \ (\text{mod }M_2) ∑xj γj ≡C (mod M2 )
这是一个线性同余方程组。其有解当且仅当 uuu 属于 uju_juj 生成的 M1M_1M1 的子群 且 CCC 属于 γj\gamma_jγj 生成的 M2M_2M2 的子群，并且这两个条件与生成元的系数在模 gcd\gcdgcd 意义下一致。
更系统的方法是：考虑所有可能的线性组合 ∑xj(uj,γj)\sum x_j (u_j, \gamma_j)∑xj (uj ,γj ) 在 Z2\mathbb{Z}^2Z2 中生成的格，然后模 M1×M2M_1 \times M_2M1 ×M2 。
用数学语言：定义群同态
ϕ:Zn→ZM1×ZM2,(x1,…,xn)↦(∑xjuj mod M1, ∑xjγj mod M2)\phi: \mathbb{Z}^n \to \mathbb{Z}_{M_1} \times \mathbb{Z}_{M_2},\quad (x_1,\dots,x_n) \mapsto \left(\sum x_j u_j \bmod M_1,\ \sum x_j \gamma_j \bmod M_2\right) ϕ:Zn→ZM1 ×ZM2 ,(x1 ,…,xn )↦(∑xj uj modM1 , ∑xj γj modM2 )
t∈L\mathbf{t} \in Lt∈L 当且仅当 t∈Imϕ\mathbf{t} \in \operatorname{Im} \phit∈Imϕ。
判断方法：解线性同余方程组。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
8. 计算最小 K 的算法思路
我们需要最小 kkk 使得存在 vi1,…,vik\mathbf{v}_{i_1},\dots,\mathbf{v}_{i_k}vi1 ,…,vik 和 ej∈[0,p−1]e_j \in [0,p-1]ej ∈[0,p−1] 满足 ∑ejvij≡t\sum e_j \mathbf{v}_{i_j} \equiv \mathbf{t}∑ej vij ≡t。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
8.1 情况 K=1
存在 iii 和 e∈[0,p−1]e \in [0,p-1]e∈[0,p−1] 使得：
eui≡u (mod M1)e u_i \equiv u \ (\text{mod }M_1) eui ≡u (mod M1 )
eγi≡C (mod M2)e \gamma_i \equiv C \ (\text{mod }M_2) eγi ≡C (mod M2 )
这等价于解 eee 在模 lcm(M1,M2)=p(p−1)\operatorname{lcm}(M_1,M_2) = p(p-1)lcm(M1 ,M2 )=p(p−1) 下的方程，但 eee 还要在 [0,p−1][0,p-1][0,p−1] 内。
实际上，从第二个方程得 e≡Cγi−1(modp)e \equiv C \gamma_i^{-1} \pmod{p}e≡Cγi−1 (modp)（如果 γi≠0\gamma_i \neq 0γi =0 模 ppp），记为 e0e_0e0 。
从第一个方程得 e≡uui−1(modp−1)e \equiv u u_i^{-1} \pmod{p-1}e≡uui−1 (modp−1)（如果 gcd(ui,p−1)=1\gcd(u_i, p-1)=1gcd(ui ,p−1)=1 才能求逆），记为 e1e_1e1 。
然后用 CRT 合并 e≡e0 (mod p)e \equiv e_0 \ (\text{mod }p)e≡e0 (mod p) 和 e≡e1 (mod p−1)e \equiv e_1 \ (\text{mod }p-1)e≡e1 (mod p−1) 得到模 p(p−1)p(p-1)p(p−1) 的解 eee，再取 eee 在 [0,p−1][0,p-1][0,p−1] 内的代表元，检查是否满足原方程。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
8.2 情况 K=2
选择 i,ji,ji,j，解
e1ui+e2uj≡u (mod M1)e_1 u_i + e_2 u_j \equiv u \ (\text{mod }M_1) e1 ui +e2 uj ≡u (mod M1 )
e1γi+e2γj≡C (mod M2)e_1 \gamma_i + e_2 \gamma_j \equiv C \ (\text{mod }M_2) e1 γi +e2 γj ≡C (mod M2 )
其中 e1,e2∈[0,p−1]e_1,e_2 \in [0,p-1]e1 ,e2 ∈[0,p−1]。
这是一个 2×22 \times 22×2 的线性方程组，可以枚举 i,ji,ji,j 并判断是否有解且在指定范围内。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
8.3 一般 K
当 k≥3k \ge 3k≥3 时，由于系数范围是 [0,p−1][0,p-1][0,p−1] 且 ppp 是质数，如果 t\mathbf{t}t 属于子群 LLL 且 kkk 足够大，则总可以构造出解（类似于硬币问题/弗罗贝尼乌斯硬币问题在二维模意义下的推广）。
但这里 kkk 最大可能到 nnn 或稍大，因为我们可以重复使用同一个向量。
定理：如果 t∈L\mathbf{t} \in Lt∈L，则 k≤2k \le 2k≤2 或 k≤3k \le 3k≤3 即可，因为我们可以用三个向量生成任意所需调整。
具体地，我们可以先用 k=2k=2k=2 尝试所有对 (i,j)(i,j)(i,j) 解方程组，如果无解则尝试 k=3k=3k=3。
k=3k=3k=3 时，我们可以固定 e3=1e_3=1e3 =1 或 e3=0e_3=0e3 =0 化为 k=2k=2k=2 问题，因此 k=3k=3k=3 的情况可被 k=2k=2k=2 包含（如果允许 ej=0e_j=0ej =0）。
所以实际最小 k 只可能是 1 或 2，除非无解。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
验证：若 k=2k=2k=2 无解，但 t∈L\mathbf{t} \in Lt∈L，则存在整数 d1,d2,d3d_1,d_2,d_3d1 ,d2 ,d3 使得 t=d1v1+d2v2+d3v3\mathbf{t} = d_1 \mathbf{v}_1 + d_2 \mathbf{v}_2 + d_3 \mathbf{v}_3t=d1 v1 +d2 v2 +d3 v3 ，我们可以令 ej=dj mod pe_j = d_j \bmod pej =dj modp 并调整，可能需要 k=3k=3k=3。
但在本题数据范围 n≤5000n \le 5000n≤5000 可枚举。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
9. 算法步骤
1. 预处理
* 若 B=0B=0B=0 则无解，因为集合 HHH 中常数项非零（单位元是 (1,0)(1,0)(1,0) 对应 0x+10x+10x+1）。
* 计算 C=AB−1(modp)C = A B^{-1} \pmod{p}C=AB−1(modp)。
* 选原根 ggg 模 ppp，预处理离散对数表（可用 BSGS 或直接枚举，因为 ppp 可到 10910^9109 但 nnn 不大，我们只对 bib_ibi 和 BBB 求离散对数，用 map 存储）。
* 对每个 iii 计算 ui=dlogg(bi)u_i = \operatorname{dlog}_g(b_i)ui =dlogg (bi )，γi=aibi−1(modp)\gamma_i = a_i b_i^{-1} \pmod{p}γi =ai bi−1 (modp)。
2. 判断无解条件
* 设 d1=gcd(u1,…,un,p−1)d_1 = \gcd(u_1,\dots,u_n, p-1)d1 =gcd(u1 ,…,un ,p−1)，d2=gcd(γ1,…,γn,p)d_2 = \gcd(\gamma_1,\dots,\gamma_n, p)d2 =gcd(γ1 ,…,γn ,p)。
* 解方程组存在整数 x1,…,xnx_1,\dots,x_nx1 ,…,xn 使得：
∑xiui≡u (mod p−1),∑xiγi≡C (mod p)\sum x_i u_i \equiv u \ (\text{mod }p-1),\quad \sum x_i \gamma_i \equiv C \ (\text{mod }p) ∑xi ui ≡u (mod p−1),∑xi γi ≡C (mod p)
的充要条件是：
d1∣u且d2∣Cd_1 \mid u \quad \text{且} \quad d_2 \mid C d1 ∣u且d2 ∣C
且这两个同余式在模 gcd(p−1,p)=1\gcd(p-1,p)=1gcd(p−1,p)=1 下自动一致（因为模数互质）。
* 若不满足，输出 −1-1−1。
3. k=1 检查
* 对每个 iii：
* 如果 γi=0\gamma_i = 0γi =0 则需 C=0C=0C=0 且 uuu 是 uiu_iui 的倍数（模 p−1p-1p−1 下）。
* 如果 γi≠0\gamma_i \neq 0γi =0，计算 e0=Cγi−1 mod pe_0 = C \gamma_i^{-1} \bmod{p}e0 =Cγi−1 modp，e1=uui−1 mod (p−1)e_1 = u u_i^{-1} \bmod{(p-1)}e1 =uui−1 mod(p−1)（需 gcd(ui,p−1)=1\gcd(u_i, p-1)=1gcd(ui ,p−1)=1 和 gcd(γi,p)=1\gcd(\gamma_i, p)=1gcd(γi ,p)=1 等条件，否则解更多情况，但可用扩展欧几里得解同余方程）。
* 用 CRT 合并 e≡e0 (mod p)e \equiv e_0 \ (\text{mod }p)e≡e0 (mod p) 和 e≡e1 (mod p−1)e \equiv e_1 \ (\text{mod }p-1)e≡e1 (mod p−1) 得到 eee 模 p(p−1)p(p-1)p(p−1) 的解，取 eee 在 [0,p−1][0,p-1][0,p−1] 内，验证两方程。
* 若有解，记录最小 eee 和对应的 iii，输出 k=1k=1k=1 和方案。
4. k=2 检查
* 枚举所有对 (i,j)(i,j)(i,j)（包括 i=ji=ji=j）：
* 解方程组
e1ui+e2uj≡u (mod p−1)e_1 u_i + e_2 u_j \equiv u \ (\text{mod }p-1) e1 ui +e2 uj ≡u (mod p−1)
e1γi+e2γj≡C (mod p)e_1 \gamma_i + e_2 \gamma_j \equiv C \ (\text{mod }p) e1 γi +e2 γj ≡C (mod p)
* 这是一个 2×22 \times 22×2 线性方程组，可用模逆解：
{e1=u−e2ujui (mod p−1)e2=C−e1γiγj (mod p)\begin{cases} e_1 = \frac{u - e_2 u_j}{u_i} \ (\text{mod }p-1) \\ e_2 = \frac{C - e_1 \gamma_i}{\gamma_j} \ (\text{mod }p) \end{cases} {e1 =ui u−e2 uj (mod p−1)e2 =γj C−e1 γi (mod p)
交替代入消元，需处理分母可逆性。
* 更稳健：用扩展欧几里得解线性丢番图方程组，并判断 e1,e2e_1,e_2e1 ,e2 是否在 [0,p−1][0,p-1][0,p−1] 内。
* 若有解，输出 k=2k=2k=2 和方案。
5. k≥3 构造
* 若 k=1,2 都无解，但之前判定有解，则可构造 k=3 解：
* 选 iii 使 γi≠0\gamma_i \neq 0γi =0，令 e1=Cγi−1 mod pe_1 = C \gamma_i^{-1} \bmod{p}e1 =Cγi−1 modp，则第二个方程满足。
* 设剩余需要 u′=u−e1ui (mod p−1)u' = u - e_1 u_i \ (\text{mod }p-1)u′=u−e1 ui (mod p−1)，用另外两个向量 j,lj,lj,l 组合出 u′u'u′ 在模 p−1p-1p−1 下，系数在 [0,p−1][0,p-1][0,p−1] 内。
* 因为 ppp 和 p−1p-1p−1 互质，可调整。
* 输出 k=3 方案。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
10. 样例验证
样例1
计算得 C=603∗648−1≡901(mod997)C = 603*648^{-1} \equiv 901 \pmod{997}C=603∗648−1≡901(mod997)，γ1=200∗61−1≡85\gamma_1 = 200*61^{-1} \equiv 85γ1 =200∗61−1≡85，u1=dlogg(61)u_1 = \operatorname{dlog}_g(61)u1 =dlogg (61), u=dlogg(648)u = \operatorname{dlog}_g(648)u=dlogg (648)。
方程组：
e⋅u1≡u(mod996)e\cdot u_1 \equiv u \pmod{996} e⋅u1 ≡u(mod996)
e⋅85≡901(mod997)e\cdot 85 \equiv 901 \pmod{997} e⋅85≡901(mod997)
从第二个方程得 e≡901∗85−1≡210(mod997)e \equiv 901*85^{-1} \equiv 210 \pmod{997}e≡901∗85−1≡210(mod997)。
用 CRT 合并 e≡210 (mod 997)e \equiv 210 \ (\text{mod }997)e≡210 (mod 997) 和 e≡uu1−1 (mod 996)e \equiv u u_1^{-1} \ (\text{mod }996)e≡uu1−1 (mod 996) 得到 e=140787e=140787e=140787（模 997∗996997*996997∗996 的解在 [0,p−1][0,p-1][0,p−1] 内）。
所以 k=1 可行，输出 1 和 1 140787。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
样例2
计算得 C=648C=648C=648，γ1=534∗750−1\gamma_1=534*750^{-1}γ1 =534∗750−1 模 953 为某值，方程组无解（因为 k=1 不行且 n=1n=1n=1 无法 k=2），输出 -1。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
样例3
p=7, p-1=6, A=6, B=5, 需自己验证 k=2 方案。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
11. 算法复杂度
* 预处理离散对数：O(np)O(n \sqrt{p})O(np ) 用 BSGS 或 O(p)O(p)O(p) 暴力，但 p 可大，n 小，可用 map 缓存。
* 判断有解：O(nlogp)O(n \log p)O(nlogp) 求 gcd。
* k=1 检查：O(nlogp)O(n \log p)O(nlogp)。
* k=2 检查：O(n2logp)O(n^2 \log p)O(n2logp)，n≤5000 可能较大，但实际可优化：枚举 iii，用哈希表存 uju_juj 和 γj\gamma_jγj 组合。
* 总复杂度在可接受范围。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
12. 实现提示
1. 用扩展欧几里得解同余方程。
2. 用 CRT 合并模 ppp 和 p−1p-1p−1 的方程。
3. 注意 γi=0\gamma_i=0γi =0 或 uiu_iui 与 p−1p-1p−1 不互素的特殊情况。
4. 离散对数用 BSGS 实现，注意 ppp 较大时用 unordered_map 存储。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
这样我们就得到了完整的解题思路和算法步骤。
知道了思路，写个代码吧
