质因数分解
inline void divide(int n){
for(register int i=2;i*i<=n;++i){
if(n%i==0){
p[++len]=i;c[len]=0;
while(n%i==0)n/=i,++c[len];
}
}
if(n>1)p[++len]=n,c[len]=1;
}
线性筛质数
inline void find(void){
memset(v,true,sizeof(v));v[1]=false;
for(register int i=2;i<=n;++i){
if(v[i]){primes[++priN]=i;}
for(register int j=1;j<=priN;++j){
if(i*primes[j]>n)break;
v[i*primes[j]]=false;
if(i%primes[j]==0)break;
}
}
}
N的正约数个数
((1+c_1) imes (1+c_2) imes ... imes (1+c_m))
N的正约数之和
((1+p_1+p_1^2+...+p_1^{c_1}) imes (1+p_2+p_2^2+...+p_2^{c_2}) imes ... imes (1+p_m+p_m^2+...+p_m^{c_m})).
更相减损术
(gcd(a,b)=gcd(b,a-b)=gcd(a,a-b)).
欧几里得算法
(gcd(a,b)=gcd(b,amod b)).
欧拉函数
(varphi (N)=N imes frac{p_1-1}{p_1} imes frac{p_2-1}{p_2} imes ... imes frac{p_m-1}{p_m}).
inline void get(void){//n log n 筛欧拉函数
for(register int i=2;i<=n;++i)phi[i]=i;
for(register int i=2;i<=n;++i){
if(phi[i]==i){
for(register int j=i;j<=n;j+=i){
phi[j]=phi[j]/i*(i-1);
}
}
}
}
扩展欧几里得算法
inline int exgcd(int a,int b,int &x,int &y){
if(b==0){x=1;y=0;return a;}
int d=exgcd(b,a%b,x,y);
int z=x;x=y;y=z-y*(a/b);
return d;
}
ax+by=c方程通解
设(d=gcd(a,b))。
如果(d|c)，则方程有解，反之无解。
通解为(x=frac{c}{d} imes x_0+frac{b}{d} imes k). (y=frac{c}{d} imes y_0-frac{a}{d} imes k).
附：整数域上的三分（求最大值）
int l=-1e9,r=1e9;
while(r-l>10){
int lmid=((l+r)>>1)-3,rmid=((l+r)>>1)+3;
if(f(lmid)<f(rmid))l=lmid;
else r=rmid;
}
int ans=-1e9;
for(register int i=l;i<=r;++i){
ans=max(ans,f(i));
}
乘法逆元
即给定a，p，求一个整数x，使得(axequiv1(mod p))
1. 费马小定理（p是质数）
因为(a^{p-1}equiv1(mod p))
所以(a imes a^{p-2}equiv 1(mod p))
2. exgcd（a、p互质）
(a xequiv 1(mod p))
(Leftrightarrow ax=1+py)
(Leftrightarrow ax-py=1)
$Leftrightarrow $exgcd(a,p,x,y)
OK.
一个小误区
负数取模。
例如我们要计算(-10mod 3)，在数学界规定(-10mod 3=2)，即((-10)div 3=-4......2)，而在C++语言中(-10\% 3=-1)，所以我们为了求出正确答案，应该ans=(a%p+p)%p，这样算出来就是(2)了。
所以凡是有可能出现负数的情况，都要这样取模，或者直接：
inline int mod(int a,int p){
return (a%p+p)%p;
}
直接调用即可。
扩展中国剩余定理
其实想通了很简单。
假设我们已经求出了方程组前(k-1)个方程的解x，现在要求第(k)个方程的解。
记(m=lcm(m_1,m_2,...,m_{k-1}))，则(x+i imes m)同样是前(k-1)个方程的解。
再来看第(k)个方程，我们无非就是求一个整数(t)，使得(x+t imes mequiv b_k(mod m_k))。
搞清楚未知数是t，已知数是(x,m,b_k,m_k)。
这不就是exgcd？（线性同余方程）
求出新的解(x'=x+t imes m)，继续做即可。
组合数
符号：（从n个数中选m个）(C_m^n)
定义式：(C_n^m=frac{n!}{m!(n-m)!})。
递推式：(C_n^m=C_{n-1}^{m-1}+C_{n-1}^m)。
性质：(C_n^m=C_{n}^{n-m})。
卡特兰数列：(Cat_n=frac{C_{2n}^n}{n+1})。
高斯消元法
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long
#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)
#define FILE(s) FILEIN(s);FILEOUT(s)
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void){
Type x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return f*x;
}
const int maxn=105;
int n;double a[maxn][maxn],x[maxn];
#define eps 1e-7
inline bool gause(void){
for(register int i=1;i<=n;++i){//枚举行
int k=i;
for(register int j=i+1;j<=n;++j){//枚举行
if(fabs(a[k][i])<fabs(a[j][i]))k=j;
}
if(fabs(a[k][i])<eps)return false;
for(register int j=i;j<=n+1;++j){//枚举列
swap(a[i][j],a[k][j]);
}
double Tmp=a[i][i];
for(register int j=i;j<=n+1;++j){//枚举列
a[i][j]/=Tmp;
}
for(register int j=1;j<=n;++j){//枚举行
if(j==i)continue;
double tmp=a[j][i];
for(register int k=i;k<=n+1;++k){//枚举列
a[j][k]-=a[i][k]*tmp;
}
}
}
for(register int i=1;i<=n;++i)x[i]=a[i][n+1];
return true;
}
int main(){
n=read<int>();
for(register int i=1;i<=n;++i){
for(register int j=1;j<=n+1;++j){
a[i][j]=read<int>();
}
}
if(!gause()){
puts("No Solution");return 0;
}
for(register int i=1;i<=n;++i)printf("%.2lf
",x[i]);
return 0;
}