简单的算法总结

标签：总结 return gcd int 素数 算法 简单 equiv mod

算法笔记

欧几里得算法求最大公约数

~又称辗转相除法，求两数的最大公约数

gcd(a,b) = gcd(b,a%b)

一般代码递归形式

int gcd(int a,int b)
{
	return b? gcd(b,a%b) :a ;
}

迭代形式

int gcd(int a,int b)
{    
	while(1)
	{
		if(b == 0)  return a;
		int temp = a%b;
		a = b;
		b = temp;
	}
	
}

性质及证明：

• 设 x 为两整数a,b的最大公约数，那么 x|a,x|b

• 整数除法具有传递性(x 能整除 a，b的任意组合)则x|a-b;(重点)

• 设x 不是 b 的因子，则 x 不是 b 和 a-b 的公因子；设x 不是 a的因子， 则 x 不是 b和 a-b 的公因子；所以gcd(a,b) = gcd(b,a-b);

• 由 a>=b可知，a可表示为a=b*q+r;则 a 减去 q 个 b 剩下的数字即为 r，所以 gcd(a,b) = gcd(b,a%b);

性质

• 若gcd(a,b)=1那么 a，b 两数互质；
• gcd(a,2a)=a;
• gcd(a,0)=a;
• gcd(a,b)=gcd(-a,b)=gcd(a,-b)=gcd(-a,-b);
• LCM(a,b)gcd(a,b)=ab(LCM为最小公倍数);
• gcd(n,n+1)=1;

筛法求素数

题目：判断 1-n 的范围内有多少素数这是一般代码

bool sushu(int n)
{
	if(n<=1) return 0;
	for(int i=2;i<=sqrt(n);i++)
	{
		if(n%2 == 0) return 0;
	}
	return 1;
}

当 n 取很大时，每判断一个数 i 是否为素数，都要枚举 sqrt(i)次,时间复杂度接近O(n*2)

方法：提前建立一张素数表，再通过查表的方式来判断素数，需要用到筛法，把表中不是素数的筛去

埃氏筛

主要内容：素数的倍数都不是素数，如2的倍数(偶数)都不是素数

用一个 prime[n] bool 数组来打表 ，prime[i]=0表示 i 是素数，prime[i]=1表示 i 不是素数

一开始都初始化为 0 ，认为都是素数，然后把不是素数的筛去(prime[i]标为 1)

//时间复杂度 O(nloglogn)
#define ll long long
long long n;
bool prime[1000005]
void ai_shai()
{
    prime[1]=1;//1不是质数
    for(ll i =2;i<=n;i++)
    if(prime[i] == 0) //如果是质数，防止产生多余步骤，比如4，6的倍数已经被2筛掉了
    {
        for(ll j=i*i; j<=n;j+=i)
            prime[j]=1; //质数的倍数都不是质数
    }
}

上述的从i*i开始筛选可以理解为，轮到3的时候，可以从3*3筛选，因为3*2已经被2*3筛去了

欧式筛(线性)

对上述算法进一步优化，有些数会被不同的素数筛多次，比如30 = 3* 10 =5* 6(3,5,6各筛一次),所以欧式筛就是在基础上，让每个合数只被最小的质因数筛一次，这可以使得时间复杂度达到O(n)的线性复杂度

](https://imgchr.com/i/aIY8u4)

bool prime[1000005];
int zyz[1000005];
int cnt=0
void ol_shai
{
	prime[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(prime[i] == 0)//如果是质数
		zyz[++cnt]=i;//记录质数的个数和数据
		
		for(int j=1;j<=cnt&&i*zyz[j]<=n;++j)
		{
			prime[i*zyz[j]]=1; //让 循环的 i 乘以已经记录的cnt个质数
			if(i%zyz[j] == 0) break;//如果zyz[i]还是i的最小质因数
            //例如 i=4的时候(cnt = 2,zyz[2]=3,zyz[1] = 2)得prime[8]=1
            //而 4%2==0,-->break ||  不再进行4*3=12 ，后面i = 6的时候会进行，即
            //**让每个合数只被最小的质因数筛一次**
		}
	}
}

康托展开

给定一个1~n的排列，求该排列在 1 ~ n 的全排列中，按字典序排名多少位

例如{1,2,3}全排列为123,132,213,231,312,321,依次变大......

算法内容

公式$`X =a_n(n-1)! +a_{n-1}(n-2)!+\dots+a_1*0!+1 $, 其中 X 代表排列中的排名， \(a_i\)代表该排列中的第 i 位数字在第 i 位其后的数字中按升序排在第几个(顺序0 为最小)。

例如 1 ~ 5排列中，求 34152的排名

第一位 3：小于3的有1，2两个 --> \(2*(5-1)!=2*4!\)

第二位4：小于4的有1，2，3(不能动)，只能比较后面四位 \(2*(5-2)!=2*3!\)

第三位1：在1，5，2中排0位

第四位数字是5：在52中排第0个

第五位固定为0\(a_n=0\)

代码实现

内容：求比指定排列小的排列个数

int num[100];
int factorial(int a)
{
  if(a==1||a==0) return 1;
  return a*factorial(a-1);
}
void cantor()
{
	int n;
	scanf("%d",&n);
    for(int i=1;i<=n;i+=)
    {
        scanf("%d",&num[i]);
        
    }
    int x=0;
    for(int i=1;i<n;i++)
    {
        int a_i = 0;
        for(int j=i+1;j<=n;j++) //a_n始终是 0
        {
            if(num[i]>num[j])  a_i++;
        }
        x+=a_i * factorial(n-i);
    }
    x+=1;//最后加一
    printf("%d\n",x);
}

逆康托展开

在1~5的排列中，求解第62位的具体排列

\(61/4! = 2\dots 13\) 首位排第2(以0位最小)

\(13/3! = 2 \dots 1\) 第二位数字在剩余数字排第 2

\(1/2! = 0 \dots 1\)

$1/1! = 1\dots 0 $

34152

int factorial(int a)
{
  if(a==1||a==0) return 1;
  return a*factorial(a-1);
}
void decantor(int x,int n)
{
    vector<int> v;//存放操作组合
    vector<int> a;//所求排列组合,即排列结果
    for(int i=1;i<=n;i++)
        	v.push_back(i);
    for(int i=n;i>=1;i--)
    {
        int r=x%factorial[i-1];
        int t=x/factorial[i-1];
        x=r;
        sort(v.begin(),v.end());
        a.push_back(v[t]);//第t+1个数
        v.erase(v.begin()+t);//去除便于sort排列
    }
}

例如：\(34152 == 2*4! + 2*3! + 0*2!+1*1!\) ,除以\(4!\)后，表示后面数字比首数字大的数有2个，也就是3，把3选出来后要记得在操作数组v中把3剔除，不然会影响数字比较大小的操作。

同余定理

给定一个正整数 m ，如果两个整数 a 和 b 满足 a - b 能够被 m 整除，即 (a-b)/m 得到一个整数，那么就称整数 a 与 b 对模 m 同余，记作 \(a\equiv b(mod m)\) 。对模 m 同余是整数的一个等价关系。

数学上，两个整数除以同一个整数，若得相同余数，则二整数同余。

其数学意义是a%m = b%m ,若 a，b作差，则相同得余数一定会被抵消掉，即(a-b)%m=0

假设 (a-b)=m*k(k是整数) ---> a=b+m*k

同余的性质

• \(a\equiv a(mod m)\)
• 如果 \(a\equiv b(mod m)\),则\(b\equiv a(mod m)\)
• 如果\(a\equiv b(modm)\)和\(b\equiv c(modm)\),则\(a\equiv c(modm)\)
• 如果a与b除以m的余数相同，那么a^n与bn除以m的余数也相同，但不一定等于原余数

如果\(a\equiv b(\mod m)\)和\(c\equiv d(\mod m)\),则

1、\((a+c)\equiv (b+d) ( \mod m)\)

2、\((a-c) \equiv (b-d) (\mod m)\)

3、\((a*c) \equiv (b*d)(\mod m)\)

4、\((a+b) \equiv c (mod m )--> a \equiv(c-b)(mod m)\)

• 如果\(ac\equiv bc(\mod m)\),那么

\(a \equiv b(mod \frac{m}{gcd(c,m)})\)

• 若有 \(a\equiv b(\mod m)且\) 且\(n|m\)，则\(a\equiv b( \mod m)\)

次方取模算法

目标 ： 求\(a^{b}\mod c\) (b是一个大数)

原理

\((a*b)\mod c=[(a \mod c)*(b \mod c)]\mod c\)

考虑到b是一个大数，直接算 ab 会很慢，所以首先把 b 转换成二进制形式（这个转换不用再写一个程序，计算机里面就是二进制保持的）

\(b=(b_nb_{n-1}\dots b_3b_2b_1b_0 )_2\)

\(b=b_0+b_1*2^1+b_2*2^2+b_4*2^4+\dots+b_{n-1}*2^{n-1}+b_n*2^n\)

\(a^b=a^{b_0+b_1*2^1+b_2*2^2+b_4*2^4+\dots+b_{n-1}*2^{n-1}+b_n*2^n}\)

\(=a^{b_0}*a^{b_1*2}*a^{b_2*2^2}*a^{b_3*2^3}*a^{b_4*2^4}+\dots +a^{b_{n-1}*2^{n-1}}+a^{b_n*2^n}\)

\(a^b\%c=(a^{b_0}*a^{b_1*2}*a^{b_2*2^2}*a^{b_3*2^3}*a^{b_4*2^4}+\dots +a^{b_{n-1}*2^{n-1}}+a^{b_n*2^n})\%c\)

设\(A_n=(a^{b_0}*a^{b_1*2}*a^{b_2*2^2}*a^{b_3*2^3}*a^{b_4*2^4}*\dots *a^{b_{n-1}*2^{n-1}}a^{b_n*2^n})\%c\)

\(A_n=[(a^{b_0}*a^{b_1*2}*a^{b_2*2^2}*a^{b_3*2^3}*a^{b_4*2^4}*\dots *a^{b_{n-1}*2^{n-1}})\%c * (a^{b_n*2^n})\%c]\%c\)

\(=[A_{n-1}*(a^{b_n*2^n})\%c]\%c\)

为了方便这里设\(K_n=(a^{b_n*2^n})\%c\)

\(A_n=(A_{n-1}*K_n)\%c\)

\(A_0=a^{b_0}\%c\)

由上可知当 bn=0时，Kn=1； 当 bn=1,Kn=Tn;

代码

int quick(int a,int b, int c)
{
	int A=1;
	int T=a%c;
	while(b!=0)
	{
        if(b&1)//判断最右边bn是不是1，如果是1，K_n=Tn递推,
        {
            A=(A*T)%c;
        }
        b>>=1;//二进制位移，从右向左读取
        T=(T*T)%c;
	}
	return A;
}

三角形面积

求法：

• 已知三顶点的坐标，求面积

\((x_1,y_1),(x_2,y_2),(x_3,y_3)\)

\(S=\frac{1}{2}|(x_2-x_1)(y_3-y_1)-(x_3-x_1)(y_2-y_1)|\)

• 已知三条边长

\(S=\sqrt{p(p-a)(p-b)(p-c)}\)

\(p=\frac{a+b+c}{2}\)

三点顺序

给出三个点，让你判断 是顺时针还是逆时针给出的

叉乘计算方法

\(|a*b|=|a||b|sin{\theta}\)

坐标表示 \((x_1*y_2-x_2*y_1)\)

ans =(x2-x1)*(y3-y1) - (y2-y1)*(x3-x1)
ans<0 顺时针
ans>0 逆时针

二分查找

#include<iostream>
using namespace std;
Template <class T>
int midsort(T a[],int n,T target)
{
	int low = 0,high = n-1,mid;
    while(low <= high)
    {
        mid = low+(high - low)/2;
        if(a[mid] = target)
            return mid;
        else if(a[mid]>target)
            high = mid - 1;
        else 
            low = mid + 1;
    }
    return -1;
}

二分递归写法

int binary_searchs(int *arr, int target, int l, int r)
  {
    if (l > r)  return -1;            
    int mid = (l + r) >> 1;
    if (arr[mid] == target) 
         return mid;
    else if (arr[mid] > target)
      binary_search(arr, target, l, mid - 1);
   else      
       binary_search(arr, target, mid + 1, r);
	}

归并排序

//思想：反复将数值元素分成2个(n/2)组数据，两个排完后把两组合并，然后变成4个一组，再把两组(每组包含四个元素)合并，完成排序
const int maxn = 100;
void merge(int A[],int L1,int L2,int R1,int R2)
    //L1,R1 L2,R2分别表示两组数据的开头和结尾的索引
{
    int i = L1,j = L2;
    int temp[maxn],index = 0;
    while(i<=R1 && j<=R2)
    {
        if (A[i] <= A[j]){
            temp[index++] = A[i++];
        }
        else{
            temp[index++] = A[j++];
        }
    }
    while(i<=R1) temp[index++] = A[i++];
    while(j<=R2) temp[index++] = A[j++];
    
    for(i = 0;i<index;i++)
        A[L1+i] = temp[i];
}
void mergeSort(int A[],int left,int right)
{
    if(left<right){//如果left和right已经相邻了，那么计算mid后left==right不会再进入循环
        int mid = (right+left)/2;
        mergeSort(A,left,mid);
        mergeSort(A,mid+1,right);
        merge(A,left,mid,mid+1,right);
    }
}

快速排序

int Pos(int A[],int left,int right)
{
    int temp = A[left];
    while(left<right)
    {
        while(left<right && A[right]>temp) right -- ;
        A[left] = A[right]; // A[left]最后处理,先把小的数移到前面
        while(left<right && A[left]<temp) left++;
        A[right] = A[left]; // 把大的数移到后面
        
    }
    A[left] = temp; // 最后把基准数移到中间
    return left;
}
// 也可以这样写
{
    while(...) r--;
    swap(a[i],a[j]);
    
    while(...) l++;
    swap(a[i],a[j]);
    
    // 最后不用交换
}

void quickSort(int A[],int left,int right)
{
    if(left<right){//当区间长度不超过1
        int pos = Pos(A[],left,right);
        quickSort(A[],left,pos-1);
        quickSort(A[],pos+1,right);//一个减1，一个加1
    }
}

在递增数组中快速找到A+B=的数

void (int A[],left,right){
    i = left;
    j = right;//i往右，j往左
    while(i<j)
    {
        if(a[i]+a[j] == m) {
            printf("%d %d\n",i,j);
       		i++;
            j--;//找到了一种方案
        }
        else if(a[i]+a[j]<m)
     	i++;
        else 
            j--;
    }
}

合并数组两个递增数组合并成一个递增数组

int merge(int A[],int B[],int C[],int m,int n)
    // m 和 n 分别是A和B的长度
{
    int i=0,j=0;
    int index = 0;
    while(i<m && i<n){
        if(A[i]<=A[j])
            C[index++] = A[i++];
        else 
            C[index++] = A[j++];
        
    }
	while(i<m) C[index++] = A[i++];
    while(j<n) C[index++] = A[j++];
    return indedx;//序列的长度
}

质因子分解

#include<cstdio>
#include<math.h>
const int maxn = 1000010;
bool is_prime(int n){//判断是否是素数
    if (n==1) return false;
    for (int i =2;i<sqrt(n);i++)
    {
        if(n%i == 0) return false;
    }
    return true;
}
int pNum = 0,prime[maxn];
void Find_prime(){//求素数表
    for (int i=2;i<maxn;i++){
        if (is_prime(i))
        prime[pNum++] = i;
    }
}
struct factor{
    int x,cnt;
}fac[10];
int main(){
    Find_prime();
    int n,num=0;
    cin>>n;
    if(n==1) cout<<"1==1";
    else{
        int sqr = (int) sqrt(1.0*n) // n的根号
        for(int i=0;i<pNum && prime[i]<sqr;i++){
            if(n%prime[i] ==0){
                fac[num].x=prime[i];//先记录第一个数字
                fac[num].cnt = 0;//进入循环后再加个数，次数
                while(n%prime[i] == 0){
                    fac[num].cnt++;
                    n /= prime[i];
                }
                    num ++;//下一个质因子
            }
            if(n==1) break;//及时退出循环,节省时间
        }
        if(n!=1){//如果无法被根号n以内的数除尽，比如108 = 59 * 2，59不满足if语句，永远进不了if判断,需要单独记录
            fac[num].x = n;
            fac[num].cnt = 1;
        }
        for(int i=0;i<num;i++)
        {
            if(i>0) cout<<"*"; 
            cout<<fac[i].x;
            if(fac[i].cnt>1)
                cout<<"^"<<"fac[i].cnt";
        }
    }
    //以上都是else里面的内容
    return 0;
}

组合数计算

//递归写法
long long C(int n,int m){
    if(m==1||m==n){
        return 1;
    }
    return C(n-1,m)+C(n-1,m-1);
}



int res[60][60] = {0};
long long C(int n,int m){
    if (m==1 || m==n) return 1;
    if(res[n][m]!=0) return res[n][m];//已经计算过的
    return res[n][m] = C(n-1,m)+C(n-1,m-1);//没有计算过的
    
}
//递归直接打表，把所有组合数即在表里
const int n = 60;
for(int i=0;i<=n;i++){
    res[i][0] = res[i][i] = 1;//初始化边界
    for (int i=2;i<=n;i++){
        for(int j =0;j<=i/2;j++){
            res[i][j] = res[i-1][j]+res[i-1][j-1];
            res[i][i-j] = res[i][j];//组合数的性质
        }
    }
}

//化简计算
long long C(int n,int m){
    ans = 1;
    for (int i=1;i<=m;i++){
        ans = ans*(n-m+i)/i;
    }
}

标签：总结,return,gcd,int,素数,算法,简单,equiv,mod
From： https://www.cnblogs.com/ddja/p/18406532