1.欧几里得求gcd
int gcd(int a,int b)
{
if(b==0) return a;
return gcd(b,a%b);
}
2.扩展欧几里得求解线性方程
首先根据Bezout定理，对于任意的a,b:ax+by=gcd(a,b);
然后根据欧几里得求gcd的方法构成等价方程，在递归的同时求出x，y；
void exgcd(int a,int b,int &x,int &y)
{
if(b==0){
x=1;y=0;
return;
}
gcd(b,a%b,y,x);
y-=a/b*x;
}
另外一种写法：(不只是long long 的事情)
void exgcd(long long a,long long b,long long& x,long long& y)
{
if(!b){
x=1;y=0;
return;
}
exgcd(b,a%b,x,y);
long long tmp=x; x=y; y=tmp-a/b*y;
}
3.扩展欧几里得求逆元
这其实与上面的求线性方程的本质是一样的，这里就不多说了
void exgcd(long long a,long long b,long long& x,long long& y)
{
if(!b){
x=1;y=0;
return;
}
exgcd(b,a%b,x,y);
long long tmp=x; x=y; y=tmp-a/b*y;
}
4.费马小定理+快速幂求逆元
long long KSM(long long a,long long b)
{
long long res=1;
while(b){
if(b&1) res=res*a%p;
a=a*a%p;
b/=2;
}
return res;
}
//inv=KSM(除数,模数-2);
5.线性递推求解逆元
k∗i+r≡0(modp)
k∗(r的逆元)+(l的逆元)≡0(modp)
(l的逆元)≡−k∗(r的逆元)(modp)
(l的逆元)≡−⌊p/i⌋∗((p%i)的逆元)(modp)
#include <bits/stdc++.h>
#define p 1000000007
using namespace std;
long long inv[100010];
int main()
{
int n;
cin>>n;
inv[1]=1;
for(int i=2;i<=n;i++){
inv[i]=(p-p/i)*inv[p%i]%p;
}
for(int i=1;i<=n;i++){
cout<<inv[i]<<" ";
}
}
6.高斯消元求解线性方程组
对于一个未知量xi，找到一个xi的系数非0，但x1~xi-1的系数都是零的方程，然后用初等行变换把其他方程的xi的系数全部消成0；
在高斯消元完成后，若存在系数都是0，但常数不是0的情况，方程无解；
通常情况下：一道题并不会直接给出n个n元一次方程组。如果给了n+1个二元方程组，那么我们可以通过相邻两个方程做差，把它变成n个n元一次方程组，然后进行高斯消元求解
#include <bits/stdc++.h>
#define eps 1e-8
using namespace std;
double a[101][102];
int n;
bool GUASS()
{
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
if(fabs(a[j][i])>eps){
for(int k=1;k<=n;k++){
swap(a[i][k],a[j][k]);
}
swap(a[i][n+1],a[j][n+1]);
break;
}
}
for(int j=1;j<=n;j++){
if(i==j) continue;
double tmp=a[j][i]/a[i][i];
for(int k=i;k<=n;k++){
a[j][k]-=a[i][k]*tmp;
}
a[j][n+1]-=a[i][n+1]*tmp;
}
}
for(int i=1;i<=n;i++){
bool lala=0;
for(int j=1;j<=n;j++){
if(a[i][j]!=0){
lala=1;
}
}
if(lala==0){
cout<<"No Solution";
return 0;
}
}
return 1;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n+1;j++){
scanf("%lf",&a[i][j]);
}
}
if(GUASS()){
for(int i=1;i<=n;i++){
printf("%.2lf
",a[i][n+1]/a[i][i]);
}
}
}
7.利用高斯消元求取矩阵的逆：
作用：求X=A/B; (X*B=A，X*B*B的逆矩阵=A*B的逆矩阵，X=A*B的逆矩阵)；(任何矩阵*单位矩阵=单位矩阵)
方法：在读入的n阶矩阵右侧加入一个n阶单位矩阵，然后做高斯消元，使读入的n阶矩阵化为n阶单位矩阵，此时右面加入的矩阵就为所求的逆。
特点：一个可逆矩阵，它的逆矩阵是唯一的;
#include <bits/stdc++.h>
#define p 1000000007
#define inc(i,a,b) for(register int i=a;i<=b;i++)
using namespace std;
int n;
int a[1000][1000];
long long KSM(long long a,long long b)
{
long long res=1;
while(b){
if(b&1) res=res*a%p;
a=a*a%p;
b/=2;
}
return res%p;
}
int Gauss()
{
inc(i,1,n){
inc(j,i,n) if(a[j][i]) {swap(a[j],a[i]);break;}
if(a[i][i]==0){cout<<"No Solution"; return 0;}
long long tmp=KSM(a[i][i],p-2);
inc(j,i,2*n) a[i][j]=a[i][j]*tmp%p;
inc(j,1,n){
if(i==j) continue;
long long tmp2=a[j][i]%p;
inc(k,i,2*n) a[j][k]=(a[j][k]-tmp2*a[i][k]%p+p)%p;
}
}
return 1;
}
int main()
{
cin>>n;
inc(i,1,n){
inc(j,1,n) scanf("%d",&a[i][j]);
a[i][i+n]=1;
}
if(Gauss()){
inc(i,1,n){
inc(j,n+1,2*n){
printf("%d ",a[i][j]);
}
printf("
");
}
}
}
8.线性筛质数
简单的模板
void prime(int n)
{
int m=0;
for(int i=2;i<=n;i++){
if(vis[i]==0){
vis[i]=i;
prime[++m]=i;
}
for(int j=1;j<=m;j++){
if(prime[j]>vis[i]||prime[j]>n/i) break;
vis[i*prime[j]]=prime[j];
}
}
}
9.线性筛求解欧拉函数
特殊的：phi[1]=1;
phi[n]=phi[n/p]*p(p是质数且p方整除n)
phi[n]=phi[n/p]*(p-1)(p是质数且p方不整除n)
void prime(int n)
{
int m=0;
for(int i=2;i<=n;i++){
if(vis[i]==0){
vis[i]=i;
prime[++m]=i;
phi[i]=i-1;
}
for(int j=1;j<=m;j++){
if(prime[j]>vis[i]||prime[j]>n/i) break;
vis[i*prime[j]]=prime[j];
phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);
}
}
}
10.O(sqrt(n))求解一个数的欧拉函数
从欧拉函数的定义而来，没什么特别的
void prime(int n)
{
int m=0;
for(int i=2;i<=n;i++){
if(vis[i]==0){
vis[i]=i;
prime[++m]=i;
phi[i]=i-1;
}
for(int j=1;j<=m;j++){
if(prime[j]>vis[i]||prime[j]>n/i) break;
vis[i*prime[j]]=prime[j];
phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);
}
}
}
11.欧拉定理的推论求解快速幂
#include <iostream>
#include <cstdio>
#include <cmath>
#define ll long long
using namespace std;
ll a,m,b;
inline ll read(ll m){
register ll x=0,f=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)){
x=x*10+ch-'0';
if(x>=m) f=1;
x%=m;ch=getchar();
}
return x+(f==1?m:0);
}
ll phi(ll n){
ll ans=n,m=sqrt(n);
for(ll i=2;i<=m;i++){
if(n%i==0){
ans=ans/i*(i-1);
while(n%i==0) n/=i;
}
}
if(n>1) ans=ans/n*(n-1);
return ans;
}
ll fast_pow(ll a,ll b,ll p){
ll ret=1;
for(;b;b>>=1,a=a*a%p)
if(b&1) ret=ret*a%p;
return ret;
}
int main()
{
cin>>a>>m;
b=read(phi(m));
cout<<fast_pow(a,b,m);
return 0;
}
12.BSGS求解高次同余方程
利用了跳过无用枚举的技巧巧妙地将O(nlogn)的算法优化成了O(sqrt(n)logn),并保证了正确性；
但是map的映射或许会加大程序的常数；
void BSGS(long long a, long long ans, long long p) {
map<long long, long long> Myhash;
ans %= p;
int tmp = sqrt(p) + 1;
for (int i = 0; i < tmp; i++) {
Myhash[(ans * KSM(a, i, p)) % p] = i;
}
a = KSM(a, tmp, p) % p;
if (a == 0 && ans == 0) {
cout << "1" << endl;
return;
}
if (a == 0 && ans != 0) {
cout << "Orz, I cannot find x!" << endl;
return;
}
for (int i = 0; i <= tmp; i++) {
if (Myhash.find(KSM(a, i, p)) != Myhash.end() && (i * tmp - Myhash[KSM(a, i, p)] >= 0)) {
cout << i * tmp - Myhash[KSM(a, i, p)] << endl;
return;
}
}
cout << "Orz, I cannot find x!" << endl;
}
updataing......