今天天我们来讲“函数”
一、一次函数（Linear Function）
1. 定义与解析式
- 一般式：y=kx+b （k,b 为常数，且 k=0）
- 特例：当 b=0 时，y=kx 为正比例函数。
- 关键：k 是斜率，b 是截距。
2. 图像特征
3. 性质速查表
| 系数 |
图像走势 |
增减性 |
| k > 0 |
上升 |
单调递增 |
| k < 0 |
下降 |
单调递减 |
4. 待定系数法
设 y=kx+b，代入两点坐标解方程组。
二、二次函数（Quadratic Function）
1. 定义与解析式
- 一般式：y=ax2+bx+c （a=0）
- 顶点式：y=a(x−h)2+k （顶点 (h,k)）
- 交点式：y=a(x−x1)(x−x2) （与x轴交点 x1,x2）
2. 图像特征
- 形状：抛物线
- 开口：a>0 向上，a<0 向下
- 对称轴：x=−2ab
- 顶点：(−2ab,4a4ac−b2)
三、例题详解（3种题型）
例题1：一次函数解析式的确定
题目：已知一次函数图像经过点 A(1,3) 和 B(−2,−3)，求函数解析式。
解答：
- 设解析式为：y=kx+b
- 将两点代入：
{3=k×1+b−3=k×(−2)+b
- 解方程组：
- 上减下：3−(−3)=k−(−2k) → 6=3k → k=2
- 代入：3=2×1+b → b=1
- 解析式为：y=2x+1
例题2：二次函数最值问题
题目：用长为24米的篱笆围一个矩形菜地，一面靠墙。问长宽各多少时面积最大？最大面积是多少？
解答：
- 建模：设与墙垂直的边长为 x 米，则与墙平行的边为 (24−2x) 米
- 列式：面积 S=x(24−2x)=−2x2+24x
- 分析：a=−2<0，开口向下，有最大值
- 求顶点（最值点）：
- 顶点横坐标：x=−2ab=−2×(−2)24=6
- 最大面积：Smax=−2×62+24×6=−72+144=72
- 答：当宽为6米，长为12米时，面积最大为72平方米。
例题3：一次函数与二次函数的综合应用
题目：某商品进价40元，售价60元时每天可卖100件。调查发现：每降价1元可多卖10件，每涨价1元则少卖10件。设售价为 x 元，日利润为 y 元。
(1) 求 y 关于 x 的函数关系式
(2) 售价定为多少时，日利润最大？最大利润是多少？
解答：
(1) 分情况建立函数：
- 当 x≤60 时（降价）：
销售量：100+10(60−x)=700−10x
单件利润：x−40
∴ y=(x−40)(700−10x)=−10x2+1100x−28000
- 当 x≥60 时（涨价）：
销售量：100−10(x−60)=700−10x（巧合，表达式相同）
单件利润：x−40
∴ y=(x−40)(700−10x)=−10x2+1100x−28000
- 注意：实际中降价和涨价的表达式通常不同，但本题数字设计导致一致。
(2) 求最值：
y=−10x2+1100x−28000
- 化为顶点式：y=−10(x−55)2+2250
- 当 x=55 时，ymax=2250
- 验证合理性：x=55<60，属于降价销售，符合模型
- 答：定价55元时利润最大，最大利润2250元。
四、解题思路总结
| 题型 |
关键步骤 |
注意事项 |
| 求解析式 |
1. 设解析式<br>2. 代点列方程<br>3. 求解系数 |
一次函数用两点，二次函数用三点或顶点信息 |
| 最值问题 |
1. 建立函数模型<br>2. 化为顶点式<br>3. 结合定义域验证 |
注意自变量实际取值范围对最值的影响 |
| 综合应用 |
1. 分段分析<br>2. 分别建模<br>3. 全局比较 |
注意条件转换，明确变量实际意义 |
五、易错提醒
- 忘记 k=0, a=0 的前提条件
- 二次函数配方错误：y=ax2+bx+c=a(x+2ab)2+4a4ac−b2
- 实际应用题忽略定义域：边长、售价、件数等必须为正整数或有范围限制
下面我们来看几道例题
题目描述
给定 n 个一次函数 fi(x)=aix+bi，其中 x 为形式幂级数的占位符。
从这 n 个中选出 k 个 gi(x) （1≤i≤k），定义集合 H 为 gi 的若干次幂的乘积模 x2 的值所构成的集合。即：
H={i=1∏kgi(x)jmodx20≤a,b<p}
其中 j 是任意非负整数且对于每个 i 可以有不同的 j。
需要注意的是，0⋅x+1 始终在集合 H 中（而非 0⋅x+0），即使 k=0 也是如此。
给定 A,B，求出所有满足 Ax+B∈H 的集合 H 的 k 的最小值。
若不存在 H 使得 Ax+B∈H，输出 -1。
所有运算均在模 p 意义下进行。
输入格式
第一行四个整数 n,p,A,B。
接下来 n 行，每行两个整数 ai,bi。
输出格式
第一行一个整数 k，表示答案。
若存在方案，接下来 k 行，每行两个整数 a,b，需满足
(∏fa(x)b)modx2=Ax+B
a 的顺序可任意。
输入输出样例 #1
输入 #1
1 997 603 648
200 61
输出 #1
1
1 140787
输入输出样例 #2
输入 #2
1 953 712 307
534 750
输出 #2
-1
输入输出样例 #3
输入 #3
3 7 6 5
3 4
5 6
4 6
输出 #3
2
2 5
1 20
说明/提示
另有两组大样例与 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≤109，保证 p 为质数，1≤n≤5×103，0≤ai,A<p，1≤bi,B<p。
详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：
| 子任务编号 |
分值 |
n |
p |
特殊性质 |
| 1 |
5 |
=1 |
≤1000 |
|
| 2 |
5 |
≤3 |
=7 |
|
| 3 |
15 |
≤100 |
=31 |
|
| 4 |
20 |
|
|
A=B=1 |
| 5 |
25 |
≤20 |
|
|
| 6 |
15 |
≤500 |
|
|
| 7 |
15 |
|
|
|
1. 题意与问题转化
我们有 n 个一次函数：
fi(x)=aix+bi,ai,bi∈Fp, bi=0
在模 p 意义下运算，p 为质数。
定义集合 H：
- 从这 n 个函数中选出 k 个 g1,…,gk（可重复选）
- 对每个 gi 选取幂指数 ei∈{0,1,…,p−1}
- 计算 ∏i=1kgi(x)eimodx2，即保留常数项和一次项
- 所有这样的结果构成 H
题目要求：给定 A,B，求最小的 k 使得存在某个 H 满足 Ax+B∈H。若不存在输出 −1。
2. 代数结构分析
记一次函数 g(x)=b+ax 为二元组 (b,a)，其中 b∈Fp∗, a∈Fp。
乘法（模 x2 截断）：
(b1,a1)⋅(b2,a2)=(b1b2, a1b2+a2b1)
单位元 e=(1,0)。
幂运算公式（可通过归纳法证明）：
(b,a)m=(bm, mbm−1a)
对任意整数 m≥0 成立。
3. 对数同构化简
令 c=ab−1(modp)，则 (b,a)=(b,bc)。
乘法规则变为：
(b1,b1c1)⋅(b2,b2c2)=(b1b2, b1b2(c1+c2))
即
(b1,c1)⋅(b2,c2)=(b1b2, c1+c2)
其中这里的 (b,c) 表示函数 b(1+cx)。
因此有群同构：
φ:G→Fp∗×Fp,(b,a)↦(b, ab−1)
逆映射为 (β,γ)↦(β,βγ)。
在新坐标下乘法简单：
(β1,γ1)∗(β2,γ2)=(β1β2, γ1+γ2)
幂运算：
(β,γ)m=(βm, mγ)
4. 问题重写
设目标函数 Ax+B 对应 (B,A)，在同构下映射为：
(B,AB−1)=(B,C)
其中 C=AB−1(modp)。
给定 n 个函数 fi=(bi,ai)，对应 (βi,γi)=(bi,aibi−1)。
对于选出的 k 个 (βi,γi) 和指数 ei∈{0,1,…,p−1}，乘积为：
j=1∏k(βj,γj)ej=(j=1∏kβjej, j=1∑kejγj)
要求等于 (B,C)，即：
j=1∏kβjej≡B(modp)(1)
j=1∑kejγj≡C(modp)(2)
其中 βj=bj∈Fp∗，γj=ajbj−1∈Fp。
5. 取离散对数
设 g 是模 p 的原根，记 βj=guj, B=gu，则方程 (1) 变为：
j=1∑kejuj≡u(modp−1)(1’)
方程 (2) 不变：
j=1∑kejγj≡C(modp)(2)
其中 ej∈{0,1,…,p−1}。
6. 问题转化为向量覆盖
记 m1=p−1, m2=p，它们互质。
对每个给定的函数 fi，定义向量：
vi=(ui,γi)∈Zm1×Zm2
目标向量：
t=(u,C)∈Zm1×Zm2
问题变为：选择 k 个向量 vi1,…,vik（可重复）和非负系数 e1,…,ek∈{0,…,p−1}，使得
j=1∑kejvij≡t(mod (m1,m2))
这里模 (m1,m2) 表示第一个分量模 m1，第二个分量模 m2。
最小化 k。
7. 最小 k 的可能值分析
7.1 可行性判定
设 S={vi} 是给定的 n 个向量。
记 L 为 S 中所有向量在 Zm1×Zm2 中生成的子群（系数取任意整数）。
记 Lp 为系数限制在 {0,1,…,p−1} 时能生成的集合。
关键观察：因为 ej 可取 0 到 p−1 任意整数，并且 p 是质数，所以对任意整数系数组合 ∑cjvj，我们可以通过给某些系数加 p 的倍数将其调整到 [0,p−1] 范围内，只要 k 足够大。
更准确地说，如果目标 t 属于 L，则存在整数 dj 使得：
t=j=1∑ndjvj
我们可对每个 dj 模 p 得到 ej∈{0,…,p−1}，但这样会改变第一个分量的值（模 m1 下）。因为 p 和 m1=p−1 互质，通过调整 k（即向量的选择）可以纠正。
结论：t 能被生成的充要条件是 t∈L，即 t 属于 S 生成的子群。
若 t∈/L，则无解，输出 −1。
7.2 判断是否属于子群
设 M1=m1=p−1, M2=m2=p。
考虑扩展向量 wi=(ui,γi,1)∈ZM1×ZM2×Z，实际上我们需要判断是否存在整数 xj 使得：
∑xjuj≡u (mod M1)
∑xjγj≡C (mod M2)
这是一个线性同余方程组。其有解当且仅当 u 属于 uj 生成的 M1 的子群 且 C 属于 γj 生成的 M2 的子群，并且这两个条件与生成元的系数在模 gcd 意义下一致。
更系统的方法是：考虑所有可能的线性组合 ∑xj(uj,γj) 在 Z2 中生成的格，然后模 M1×M2。
用数学语言：定义群同态
ϕ:Zn→ZM1×ZM2,(x1,…,xn)↦(∑xjujmodM1, ∑xjγjmodM2)
t∈L 当且仅当 t∈Imϕ。
判断方法：解线性同余方程组。
8. 计算最小 k 的算法思路
我们需要最小 k 使得存在 vi1,…,vik 和 ej∈[0,p−1] 满足 ∑ejvij≡t。
8.1 情况 k=1
存在 i 和 e∈[0,p−1] 使得：
eui≡u (mod M1)
eγi≡C (mod M2)
这等价于解 e 在模 lcm(M1,M2)=p(p−1) 下的方程，但 e 还要在 [0,p−1] 内。
实际上，从第二个方程得 e≡Cγi−1(modp)（如果 γi=0 模 p），记为 e0。
从第一个方程得 e≡uui−1(modp−1)（如果 gcd(ui,p−1)=1 才能求逆），记为 e1。
然后用 CRT 合并 e≡e0 (mod p) 和 e≡e1 (mod p−1) 得到模 p(p−1) 的解 e，再取 e 在 [0,p−1] 内的代表元，检查是否满足原方程。
8.2 情况 k=2
选择 i,j，解
e1ui+e2uj≡u (mod M1)
e1γi+e2γj≡C (mod M2)
其中 e1,e2∈[0,p−1]。
这是一个 2×2 的线性方程组，可以枚举 i,j 并判断是否有解且在指定范围内。
8.3 一般 k
当 k≥3 时，由于系数范围是 [0,p−1] 且 p 是质数，如果 t 属于子群 L 且 k 足够大，则总可以构造出解（类似于硬币问题/弗罗贝尼乌斯硬币问题在二维模意义下的推广）。
但这里 k 最大可能到 n 或稍大，因为我们可以重复使用同一个向量。
定理：如果 t∈L，则 k≤2 或 k≤3 即可，因为我们可以用三个向量生成任意所需调整。
具体地，我们可以先用 k=2 尝试所有对 (i,j) 解方程组，如果无解则尝试 k=3。
k=3 时，我们可以固定 e3=1 或 e3=0 化为 k=2 问题，因此 k=3 的情况可被 k=2 包含（如果允许 ej=0）。
所以实际最小 k 只可能是 1 或 2，除非无解。
验证：若 k=2 无解，但 t∈L，则存在整数 d1,d2,d3 使得 t=d1v1+d2v2+d3v3，我们可以令 ej=djmodp 并调整，可能需要 k=3。
但在本题数据范围 n≤5000 可枚举。
9. 算法步骤
-
预处理
- 若 B=0 则无解，因为集合 H 中常数项非零（单位元是 (1,0) 对应 0x+1）。
- 计算 C=AB−1(modp)。
- 选原根 g 模 p，预处理离散对数表（可用 BSGS 或直接枚举，因为 p 可到 109 但 n 不大，我们只对 bi 和 B 求离散对数，用
map 存储）。
- 对每个 i 计算 ui=dlogg(bi)，γi=aibi−1(modp)。
-
判断无解条件
- 设 d1=gcd(u1,…,un,p−1)，d2=gcd(γ1,…,γn,p)。
- 解方程组存在整数 x1,…,xn 使得：
∑xiui≡u (mod p−1),∑xiγi≡C (mod p)
的充要条件是：d1∣u且d2∣C
且这两个同余式在模 gcd(p−1,p)=1 下自动一致（因为模数互质）。
- 若不满足，输出 −1。
-
k=1 检查
- 对每个 i：
- 如果 γi=0 则需 C=0 且 u 是 ui 的倍数（模 p−1 下）。
- 如果 γi=0，计算 e0=Cγi−1modp，e1=uui−1mod(p−1)（需 gcd(ui,p−1)=1 和 gcd(γi,p)=1 等条件，否则解更多情况，但可用扩展欧几里得解同余方程）。
- 用 CRT 合并 e≡e0 (mod p) 和 e≡e1 (mod p−1) 得到 e 模 p(p−1) 的解，取 e 在 [0,p−1] 内，验证两方程。
- 若有解，记录最小 e 和对应的 i，输出 k=1 和方案。
-
k=2 检查
- 枚举所有对 (i,j)（包括 i=j）：
- 解方程组
e1ui+e2uj≡u (mod p−1)
e1γi+e2γj≡C (mod p)
- 这是一个 2×2 线性方程组，可用模逆解：
{e1=uiu−e2uj (mod p−1)e2=γjC−e1γi (mod p)
交替代入消元，需处理分母可逆性。
- 更稳健：用扩展欧几里得解线性丢番图方程组，并判断 e1,e2 是否在 [0,p−1] 内。
- 若有解，输出 k=2 和方案。
-
k≥3 构造
- 若 k=1,2 都无解，但之前判定有解，则可构造 k=3 解：
- 选 i 使 γi=0，令 e1=Cγi−1modp，则第二个方程满足。
- 设剩余需要 u′=u−e1ui (mod p−1)，用另外两个向量 j,l 组合出 u′ 在模 p−1 下，系数在 [0,p−1] 内。
- 因为 p 和 p−1 互质，可调整。
- 输出 k=3 方案。
10. 样例验证
样例1
1 997 603 648
200 61
计算得 C=603∗648−1≡901(mod997)，γ1=200∗61−1≡85，u1=dlogg(61), u=dlogg(648)。
方程组：
e⋅u1≡u(mod996)
e⋅85≡901(mod997)
从第二个方程得 e≡901∗85−1≡210(mod997)。
用 CRT 合并 e≡210 (mod 997) 和 e≡uu1−1 (mod 996) 得到 e=140787（模 997∗996 的解在 [0,p−1] 内）。
所以 k=1 可行，输出 1 和 1 140787。
样例2
1 953 712 307
534 750
计算得 C=648，γ1=534∗750−1 模 953 为某值，方程组无解（因为 k=1 不行且 n=1 无法 k=2），输出 -1。
样例3
3 7 6 5
3 4
5 6
4 6
p=7, p-1=6, A=6, B=5, 需自己验证 k=2 方案。
11. 算法复杂度
- 预处理离散对数：O(np) 用 BSGS 或 O(p) 暴力，但 p 可大，n 小，可用 map 缓存。
- 判断有解：O(nlogp) 求 gcd。
- k=1 检查：O(nlogp)。
- k=2 检查：O(n2logp)，n≤5000 可能较大，但实际可优化：枚举 i，用哈希表存 uj 和 γj 组合。
- 总复杂度在可接受范围。
12. 实现提示
- 用扩展欧几里得解同余方程。
- 用 CRT 合并模 p 和 p−1 的方程。
- 注意 γi=0 或 ui 与 p−1 不互素的特殊情况。
- 离散对数用 BSGS 实现，注意 p 较大时用
unordered_map 存储。
这样我们就得到了完整的解题思路和算法步骤。
知道了思路，写个代码吧
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,p,A,B;
int a[5005],b[5005];
int g,u[5005],c[5005];
map<int,int>mp;
int dlog(int x){
if(mp.count(x))return mp[x];
int t=1;
for(int i=1;i<=p-1;i++){
t=1ll*t*g%p;
if(t==x)return mp[x]=i;
}
return mp[x]=-1;
}
ll exgcd(ll a,ll b,ll&x,ll&y){
if(!b){x=1;y=0;return a;}
ll d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
ll inv(ll a,ll m){
ll x,y;
exgcd(a,m,x,y);
return (x%m+m)%m;
}
bool crt(ll a1,ll m1,ll a2,ll m2,ll&x){
ll k=a2-a1;
ll g=gcd(m1,m2);
if(k%g)return 0;
ll M=m1/g*m2;
ll t=(k/g)%(m2/g);
ll inv_m1=inv(m1/g,m2/g);
t=t*inv_m1%(m2/g);
x=(a1+m1*t)%M;
if(x<0)x+=M;
return 1;
}
bool check1(int i,ll&e){
int ui=u[i],ci=c[i];
if(ci==0){
if(A!=0)return 0;
ll x;
if(!linear_congruence(ui,u,p-1,x))return 0;
e=x;
if(e>=p)return 0;
ll t1=1,t2=0;
for(int k=0;k<e;k++){
t2=(t2*b[i]+t1*a[i])%p;
t1=t1*b[i]%p;
}
return t1==B&&t2==A;
}
ll e0=1ll*A*inv(B,p)%p*inv(ci,p)%p;
ll e1;
if(!linear_congruence(ui,u,p-1,e1))return 0;
if(!crt(e0,p,e1,p-1,e))return 0;
if(e>=p)return 0;
ll t1=1,t2=0;
for(int k=0;k<e;k++){
t2=(t2*b[i]+t1*a[i])%p;
t1=t1*b[i]%p;
}
return t1==B&&t2==A;
}
bool solve2(int i,int j,ll&e1,ll&e2){
int ui=u[i],uj=u[j],ci=c[i],cj=c[j];
ll a1=ui,b1=uj,c1=u;
ll a2=ci,b2=cj,c2=A*inv(B,p)%p;
ll det=a1*b2-a2*b1;
ll det1=c1*b2-c2*b1;
ll det2=a1*c2-a2*c1;
if(det%gcd(p-1,p)!=0)return 0;
ll m=p-1;
ll M=1ll*(p-1)*p;
ll x1,x2;
if(!linear_congruence(det,det1,M,x1))return 0;
if(!linear_congruence(det,det2,M,x2))return 0;
e1=(x1%M+M)%M;
e2=(x2%M+M)%M;
if(e1>=p||e2>=p)return 0;
ll t1=1,t2=0;
for(int k=0;k<e1;k++){
t2=(t2*b[i]+t1*a[i])%p;
t1=t1*b[i]%p;
}
for(int k=0;k<e2;k++){
t2=(t2*b[j]+t1*a[j])%p;
t1=t1*b[j]%p;
}
return t1==B&&t2==A;
}
int main(){
ios::sync_with_stdio(0);
cin>>n>>p>>A>>B;
for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
if(B==0){cout<<-1;return 0;}
for(g=2;g<p;g++){
int t=1,ok=1;
for(int j=1;j<p-1;j++){
t=1ll*t*g%p;
if(t==1){ok=0;break;}
}
if(ok)break;
}
mp.clear();
mp[1]=0;
for(int i=1;i<=n;i++){
u[i]=dlog(b[i]);
c[i]=1ll*a[i]*inv(b[i],p)%p;
}
int U=dlog(B);
int C=1ll*A*inv(B,p)%p;
int d1=p-1,d2=p;
for(int i=1;i<=n;i++){
d1=gcd(d1,u[i]);
d2=gcd(d2,c[i]);
}
if(U%d1!=0||C%d2!=0){
cout<<-1;
return 0;
}
ll e;
for(int i=1;i<=n;i++){
if(check1(i,e)){
cout<<1<<"\n"<<i<<" "<<e;
return 0;
}
}
ll e1,e2;
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
if(solve2(i,j,e1,e2)){
cout<<2<<"\n";
if(e1>0)cout<<i<<" "<<e1<<"\n";
if(e2>0)cout<<j<<" "<<e2<<"\n";
return 0;
}
}
}
cout<<-1;
return 0;
}
有帮助，赞一个