三分
求单峰函数的最小值时，每次扔掉较大的一段。
求单峰函数的最大值时，每次扔掉较小的一段。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a[10000+10],b[10000+10],c[10000+10];
double f(double x){
double ret=-1e18;
for(ll i=1;i<=n;i++)
ret=max(ret,a[i]*x*x+b[i]*x+c[i]);
return ret;
}
int main(){
int T;
cin >> T;
while(T--){
cin >> n;
for(ll i=1;i<=n;i++)cin >> a[i] >> b[i] >> c[i];
double l=0,r=1000,lmid,rmid;
while(abs(l-r)>1e-12){
lmid=l+(r-l)/3,rmid=r-(r-l)/3;
if(f(lmid)>f(rmid)){
l=lmid;
}else{
r=rmid;
}
}
cout << fixed << setprecision(4) << f((l+r)/2) << endl;
}
return 0;
}
裴蜀定理
若\(a_1 x_1 + a_2 x_2 + a_3 x_3 + ...... + a_n x_n = c\),则\(c\)是\(gcd(a_1,a_2,a_3,......,a_n)\)的倍数
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a[20+10],ans;
int main(){
cin >> n;
for(ll i=1;i<=n;i++)cin >> a[i],a[i]=abs(a[i]);
ans=a[1];
for(ll i=2;i<=n;i++)ans=__gcd(ans,a[i]);
cout << ans;
return 0;
}
矩阵快速幂
乘法逆元