听说明天AU爷ysy要给我们讲数论
赶紧预习一下好了
①高斯消元
嗯这个就不多解释了…
题1 bzoj1013 球形空间产生器
嗯这题就是给你一个n维球体上的n+1个点，求圆心。
所以假设第i个点是(a[i][1],a[i][2]…a[i][n])
那么我们就是要找一个点(x[1]…x[n])使得
(a[i][1]-x[1])^2+(a[i][2]-x[2])^2+…+(a[i][n]-x[n])^2=r^2
那么我们就有这样n+1个式子：
(a[1][1]-x[1])^2+(a[1][2]-x[2])^2+…+(a[1][n]-x[n])^2=r^2
(a[2][1]-x[1])^2+(a[2][2]-x[2])^2+…+(a[2][n]-x[n])^2=r^2
...
(a[n+1][1]-x[1])^2+(a[n+1][2]-x[2])^2+…+(a[n+1][n]-x[n])^2=r^2
那么我们把这n+1个式子两两对减，就会得到一坨类似这样的式子：
然后高斯消元即可.
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <algorithm> #include <string.h> #include <vector> #include <math.h> #include <limits> #include <set> #include <map> using namespace std; typedef double ld; #define SZ 233 namespace Gauss { ld gd[SZ][SZ+1],ans[SZ]; bool isfree[SZ]; void gauss(int n) { int cur=1; for(int i=1;i<=n;i++) { isfree[i]=0; int tg=0; for(int j=cur;j<=n;j++) if(fabs(gd[j][i])>1e-6) {tg=j; break;} if(!tg) {isfree[i]=1; continue;} for(int j=1;j<=n;j++) swap(gd[cur][j],gd[tg][j]); for(int j=1;j<=n;j++) { if(j==cur||fabs(gd[j][i])<1e-6) continue; ld bs=gd[j][i]/gd[cur][i]; for(int k=1;k<=n+1;k++) gd[j][k]-=bs*gd[cur][k]; } ++cur; } for(int i=1;i<=n;i++) { if(isfree[i]) continue; for(int j=1;j<=n;j++) { if(fabs(gd[j][i])>1e-6) ans[i]=gd[j][n+1]/gd[j][i]; } } } } int n; ld as[SZ][SZ]; void pre() { scanf("%d",&n); for(int i=1;i<=n+1;i++) { for(int j=1;j<=n;j++) scanf("%lf",&as[i][j]); if(i==1) continue; for(int j=1;j<=n;j++) { Gauss::gd[i-1][j]=2*(as[i][j]-as[i-1][j]); Gauss::gd[i-1][n+1]+=as[i][j]*as[i][j]-as[i-1][j]*as[i-1][j]; } } } int main() { using namespace Gauss; pre(); gauss(n); for(int i=1;i<=n;i++) printf("%.3lf%c",ans[i],(i!=n)?‘ ‘:‘\n‘); }
②exgcd
这种傻逼玩意儿不用我说了吧
求一组x,y使得ax+by=1。如果(a,b)≠1就无解。
我们先求出bx‘+(a%b)y‘=1的解x‘、y‘。
那么设a=pb+q(0<=q<b)。所以bx‘+qy‘=1。
所以bx‘+(a-pb)y‘=1。
所以ay‘+b(x‘-py‘)=1。
即ay‘+b(x‘-(a/b)y‘)=1。
这样就求出了一组可行解。
代码稍后放出。
③BSGS
正常的BSGS：求一个最小的非负数x使得a^x=b（mod c），其中c为质数。
首先我们肯定知道x<c-1嘛
额我们设x=pg+m(0<=m<g)，这个g是啥等会儿再说。
那么a^(pg+m)=b（mod c）
我们稍微搞一下变成a^(gp)=b*a^(-m) （mod c）
然后我们发现枚举一下p然后把a^(gp)哈希(map)一下然后右边枚举一下exgcd(费马小定理)一下在哈希表(map)里面查一下就行了。
复杂度大概是O((g+c/g)logc)或者O(g+c/g)，所以我们令g=sqrt(c)就可以做到科学的O(sqrt(c)logc)或O(sqrt(c))了。
扩展的BSGS：（方老师写的写错了不要打我）
例二 bzoj2242 计算器
搞这种三合一的题啊，excited
似乎特判十分多的样子
代码待补 碎觉
原文：http://www.cnblogs.com/zzqsblog/p/5397304.html