《算法笔记》第五章

最大公约数

求最大公约数一般用辗转相除法，代码如下

1
2
3
4
int gcd(int a, int b){
  if(b==0)return a;
  else return gcd(b,a%b);
}

最小公倍数

最小公倍数的求解要基于最大公约数

a和b的最大公约数为d，则最小公倍数为a/d∗ba/d*b

分数

我们可以用一个结构体来表示分数，一般假分数比带分数用的多，所以只需要分子和分母两个变量即可。分数的计算可能会使分子或者分母超出int的范围，所以分数中的分子分母用long long来存储。

1
2
3
struct Fraction(){
  int up,down;
}

而分子和分母当然不是任意的，需要满足以下规则

  1. 如果分数为负，则分子为负
  2. 如果分数为0，则分子为0，分母为1
  3. 分子和分母没有除了1以外的公约数

但很多时候我们会对分数进行运算，可能运算完就不满足上述的规则了，于是就需要一个函数来对分数进行化简

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Fraction reduction(Fraction result){
  if(result.down<0){
    result.up=-result.up;
    result.down=-result.down;
  }
  if(result.up==0){
    result.down=1;
  }else{
    int d=gcd(abs(result.up),result.down);
    result.up/=d;
    result.down/=d;
  }
  return result;
}

分数的计算

乘法

1
2
3
4
5
6
Fraction multi(Fraction f1,Fraction f2){
  Fraction result;
  result.up=f1.up*f2.up;
  result.down=f1.down*f2.down;
  return reduction(result);
}

除法

1
2
3
4
5
6
Fraction divide(Fraction f1,Fraction f2){
  Fraction result;
  result.up=f1.up*f2.down;
  result.down=f1.down*f2.up;
  return reduction(result);
}

加法

1
2
3
4
5
6
Fraction multi(Fraction f1,Fraction f2){
  Fraction result;
  result.up=f1.up*f2.down+f2.up*f2.down;//减法此处换成减号即可
  result.down=f1.down*f2.down;
  return reduction(result);
}

分数的输出

  1. 输出前先化简
  2. 假分数输出时要转化为带分数
  3. 分母为1的分数转化为整数输出
1
2
3
4
5
6
7
8
9
10
void showresult(Fraction r){
  r=reduction(r);
  if(r.down==1){
    printf("%lld",r.up);}
  else if(abs(r.up)>r.down){//注意这里要加绝对值
    printf("%d %d/%d",r.up/r.down,abs(r.up)%r.down,r.down);
  }else{
    printf("%d/%d",r.up,r.down);
  }
}

素数

素数的判断

1
2
3
4
5
6
7
8
9
#include<math.h>
bool isPrime(int n){
  if(n<=1) return false;
  int sqr=(int)sqrt(1.0*n);//sqrt的对象只能是浮点数所以先乘上1.0
  for(int i=2;i<=sqr;i++){
    if(n%i==1) return false;
  }
  return true;
}

素数表

因为素数的倍数一定不是素数，所以筛去这部分剩下的就是素数

1
2
3
4
5
6
7
8
9
10
11
12
13
const int maxn=表长;
bool p[maxn]={0};//素数为false
int prime[maxn],pnum;//存放素数，素数个数
void findprime(){
  for(int i=2;i<maxn;i++){//注意i不能取maxn
    if(p[i]==false){
      prime[pnum++]=i;
      for(int j=2*i;j<maxn;j+=i){//注意j不能取maxn
        p[j]=true;
      }
    }
  }
}

质因式分解

一个正整数n的质因子只有两种可能，一种一个大于sqrt其他小于，另一种所有质因子都小于sqrt。

所以只需先枚举小于sqrt的素数，判断是否是因子，然后将其除去，若除以所有因子后n仍大于1，则说明n还剩一个大于sqrt的因子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct factor{
  int x,cnt;//x为因子，cnt为个数
}fac[10];//10个足够应对int类型了

if(n==1)printf("1=1");
int num=0;
for(int i=0;i<pnum&&prime[i]<=sqrt;i++){
  if(n%prime[i]==0){
    fac[num].x=prime[i];
    fac[num].cnt=0;
    while(n%prime[i]==0){
      n/=prime[i];
      fac[num].cnt++;
    }
    num++;
  }
  if(n==1)break;
}
if(n!=1){
  fac[num].x=n;
  fac[num++].cnt=1;
}

大数

讨论极大数的运算（超出int和long的范围）

存储

用一个结构体存储，包含存储数值的数组以及长度

1
2
3
4
5
6
7
8
struct bign{
  int d[1000];
  int len;
  bign(){
    memset(d,0,sizeof(d));//把数组归0
    len=0;
  }
}；

读取时先用字符串的形式读入，再把字符串转化为bign结构体

1
2
3
4
5
6
7
8
bign change(char str[]){
  bign a;
  a.len=strlen(str);
  for(int i=0;i<a.len;i++){
    a.d[i]=str[a.len-i-1]-'0';//逆着赋值
  }
  return a;
}

比较大小也很简单，先比len，若len相就从最高位依次比较

1
2
3
4
5
6
7
8
9
10
11
int compare(bign a,bign b){
  if(a.len>b.len) return 1;
  else if(a.len<b.len) return -1;
  else{
    for (int i=a.len-1;i>=0;i--){
      if(a.d[i]>b.d[i]){return 1;}
      else if(a.d[i]<b.d[i]){return -1;}
    }
    return 0;
  }
}

运算

加法

1
2
3
4
5
6
7
8
9
10
11
12
13
bign add(bign a,bign b){
  bign c;
  int carry=0;//进位
  for(int i=0;i<a.len||i<b.len;i++){
    int temp=a.d[i]+b.d[i]+carry;
    c.d[c.len++]=temp%10;
    carry=temp/10;
  }
  if(carry!=0){
    c.d[c.len++]=carry;
  }
  return c;
}

减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bign sub(bign a,bign b){
  bign c;
  for (int i=0;i<a.len||i<b.len;i++){
    if(a.d[i]<b.d[i]){
      a.d[i+1]--;
      a.d[i]+=10;
    }
    c.d[c.len++]=a.d[i]-b.d[i];
  }
  while(c.len-1>=1&&c.d[c.len-1]==0){
    c.len--;
  }
  return c;
}

乘法（与低精度）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bign multi(bign a,int b){
  bign c;
  int carry=0;
  for(int i=0;i<a.len;i++){
    int temp=a.d[i]*b+carry;
    c.d[c.len++]=temp%10;
    carry=temp/10;
  }
  while(carry!=0){//注意乘法的进位可能不止一位
    c.d[c.len++]=carry%10;
    carry/=10;
  }
  return c;
}

除法（与低精度）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bign divide(bign a,int b,int& r){//r为余数
  bign c;
  c.len=a.len;
  for(int i=a.len-1;i>=0;i--){
    r=r*10+a.d[i];
    if(r<b) c.d[i]=0;
    else{
      c.d[i]=r/b;
      r=r%b;
    }
  }
  while(c.len-1>=1&&c.d[c.len-1]==0){//除去商前面多于的0
    c.len--;
  }
  return c;
}

扩展欧几里得算法

ax+by=gcd(a,b)ax+by=gcd(a,b)

首先易得必有x=1,y=0这组解，以此为递归边界不断计算gcd(b,a%b)gcd(b,a\%b)，得到递推公式为x1=y2,y1=x2−(a/b)y2x1=y2,y1=x2-(a/b)y2

1
2
3
4
5
6
7
8
9
10
11
12
int exGcd(int a,int b,int &x,int &y){
  if(b==0){
    x=1;
    y=0;
    return a;
  }
  int g=exGcd(b,a%b,x,y);
  int temp=x;
  x=y;
  y=temp-a/b*y;
  return g;
}

ax+by=cax+by=c

根据上述结论，该方程存在解的充要条件是c%gcd=0c\%gcd=0，且一组解为(cx0/gcd,cy0/gcd)(cx0/gcd,cy0/gcd)

全部解的公式为x’=cx0/gcd+b/gcd∗K,y’=cy0/gcd−a/gcd∗Kx’=cx0/gcd+b/gcd*K,y’=cy0/gcd-a/gcd*K（K为任意整数）

(ax−c)%m=0(ax-c)\%m=0

先求解ax+my=gcd(a,m)ax+my=gcd(a,m)，然后代入x=cx0/gcd(a,m),y=cy0/gcd(a,m)x=cx0/gcd(a,m),y=cy0/gcd(a,m)

得到x’=x+m/gcd(a,m)∗K,y’=y−a/gcd(a,m)∗Kx’=x+m/gcd(a,m)*K,y’=y-a/gcd(a,m)*K（K为任意整数）

组合数

n!的质因子

n!有（n/p+n/p^2^+n/p^3^+……）个质因子p

1
2
3
4
5
6
7
8
int cal(int n,int p){
  int ans=0;
  while(n){
    ans+=n/p;
    n/=p;
  }
  return ans;
}

组合数计算

Cnm=n!m!(n−m)!C_{n}^{m}=\frac{n!}{m!(n-m)!}

1
2
3
4
long long C(long long n,long long m){
  if(m==0||n==n)return 1;
  return C(n-1,m)+C(n-1,m-1);
}

Cnm%pC_{n}^{m}\%p

1
2
3
4
5
6
int res[1010][1010]={0};
int C(int n, int m, int p){
  if(m==0||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))%p;
}