【PAT】2. 数学问题

最大公约数与最小公倍数

求解最大公约数

欧几里得算法：设a，b均为正整数，则 g c d ( a , b ) = g c d ( b , a % b ) gcd(a,b)=gcd(b,a\%b) gcd(a,b)=gcd(b,a%b)，gcd(a,b)来表示a和b的最大公约数

递归边界为

gcd(a,0) = a

，零和任何一个整数a的最大公约数都是a

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

或者

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

求解最小公倍数

一般用lcm(a, b)来表示a和b的最小公倍数，在求得a和b的最大公约数d之后，可以得到a和b的最小公倍数是

ab/d

，可以借助集合来理解这个公式。因为a*b可能会溢出，所以一般写成

a/d*b

。

分数的四则运算

分数的表示

struct Fraction{//分数
    int up, dpwn;//分子，分母
};

对分数的这种表示指定三项规则：

使down为非负数。如果分数为负，那么令分子up为负即可
如果该分数恰为0，那么规定其分子为0，分母为1
分子和分母没有除了1以外的公约数

分数的化简：

如果分母down为负数，那么令分子up和分母down都变为相反数（使down为非负数）
如果分子up为0，那么令分母down为1
约分：求出分子绝对值与分母绝对值的最大公约数d，然后令分子分母同时除以d

分数的输出：

输出分数前要对其化简
如果分数r的分母down为1，说明是整数，直接输出分子
如果分数r的分子up绝对值大于分母down，说明分数是假分数，应按带分数的形式输出，即整数部分为 r.up/r.down ，分子部分为 abs(r.up)%r.down ，分母部分为 r.down 。

注意：由于分数的乘法和除法过程中可能使分子或分母超过int型表示范围，因此一般情况下分子和分母使用long long型存储

素数

判断n是否是素数：判定它是否能被 2 , 3 , . . . , ⌊ s q r t ( n ) ⌋ 2,3,...,\left \lfloor sqrt(n) \right \rfloor 2,3,...,⌊sqrt(n)⌋中的一个整除，时间复杂度为 O ( s q r t ( n ) ) O(sqrt(n)) O(sqrt(n))

从1~n进行枚举，判断每个数是否是素数，就能获取一个素数表，时间复杂度为 O ( n n ) O(n\sqrt{n}) O(nn

)

更高效的埃氏筛法时间复杂度为 O ( n l o g l o g n ) O(nloglogn) O(nloglogn)，关键在于“筛”。算法从小到大枚举所有数，对每一个素数，筛取它的所有倍数剩下的就都是素数。

假设从小到大到达某数a时，a没有被前面的步骤筛去，那么a一定是素数。因为如果a不是素数，那么a一定有小于a的素因子，这样在之前的步骤中a一定会被筛掉。

质因子分解

质因子分解是指将一个正整数n写成一个或者多个质数的乘积的形式。

每个质因子可以出现不止一次，因此定义结构体factor，存放质因子及其个数

struct factor{
    int x, cnt; //x为质因子，cnt为其个数
}fac[10];

考虑到

2*3*5*7*11*13*17*19*23*29

已经超过了int范围，因此对一个int型的数来说，fac数组大小只需要开到10就可以了

核心原理：对整数n来说，如果它存在[2,n]范围内的质因子，要么这些质因子全部小于等于sqrt(n)，要么只存在一个大于sqrt(n)的质因子，而其余质因子全部小于等于sqrt(n)。算法时间复杂度为 O ( n ) O(\sqrt{n}) O(n

)

枚举1~sqrt(n)内的所有质因子p，判断p是否是n的因子
- 如果p是因子，给fac数组中增加质因子p，初始化其个数为0.然后只要p还是n的因子，就让n不断除以p，每次操作令p的个数加1，直到p不再是n的因子为止
- 如果p不是因子，则跳过。
```
if(n % prime[i] == 0){
    fac[num].x = n;
    fac[num].cnt = 0;
    while(n % prime[i] == 0){
        fac[num].cnt++;
        n /= prime[i];
    }
    num++;
}
           
```
如果上面步骤结束后n仍然大于1，说明n有且仅有一个大于srqt(n)的质因子（有可能是n本身），这时将这个质因子加入fac数组，并令其个数为1.
```
if(n != 1){
    fac[num].x = n;
    fac[num++].cnt = 1;
}
           
```

大整数存储

按顺位存储：整数的高位存储在数组的高位，整数的低位存储在数组的低位。如整数235813，有d[0]=3,d[1]=1.d[2]=8,d[3]=5,d[4]=3,d[5]=2。原因是进行运算的时候都是从整数的低位到高位进行枚举。因此注意当把整数按字符串%s读入的时候，实际上是逆位存储的，即str[0]=‘2’,str[1]=‘3’,…,str[5]=‘3’，因此在读入后需要在另存至d[]数组的时候反转一下。

扩展欧几里得算法

扩展欧几里得算法
方程ax+by=c的求解
同余式ax=c(mod m)的求解
逆元的求解

组合数

求n!中有多少个质因子p

直观的想法是计算1~n中的每个数各有多少个质因子p，然后将结果累加，时间复杂度为

O(nlogn)

由 n!中有 ( n p + n p 2 + n p 3 + ⋯ ) \left ( \frac{n}{p}+\frac{n}{p^2}+\frac{n}{p^3}+\cdots \right ) (pn+p2n+p3n+⋯)个质因子p，可以得到 O ( l o g n ) O(logn) O(logn)的算法

//计算n！中有多少质因子p
int cal(int n, int p){
    int ans = 0;
    while(n){
        ans += n/p;//累加n/p^k
        n /= p;
    }
    return ans;
}

利用这个算法可以很快计算出n!的末尾有多少零：由于末尾0的个数等于n!中因子10的个数，这又等于n!中质因子5的个数，只需要带入cal(n,5)即可求出结果。

n!中质因子p的个数，实际上等于1~n中p的倍数的个数n/p加上(n/p)!中质因子p的个数，递归代码如下

int cal(int n, int p){
    if(n < p) return 0;
    return n / p + cal(n / p, p);
}

组合数的计算

计算 C n m C^m_n Cnm

通过递推公式计算： C n m = C n − 1 m + C n − 1 m − 1 C_{n}^{m} = C_{n-1}^{m} +C _{n-1}^{m-1} Cnm=Cn−1m+Cn−1m−1，递归终点为 C n 0 = C n n = 1 C_{n}^{0} = C_{n}^{n}=1 Cn0=Cnn=1

long long res[67][67] = {0};
long long C(long long n, long long m){
    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);
}

通过定义式的变形来计算，时间复杂度为

O(m)

long long C(long long n, long long m){
    long long ans = 1;
    for(long long i = 1; i <= m; i++){
        ans = ans * (n - m + i) / i;//注意一定要先乘再除
    }
    return ans;
}

计算 C n m % p C^m_n\%p Cnm%p

递归

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;
}

递推

void calC(){
    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][j-1]+res[i-1][j-1]) % p;
            res[i][i-j] = res[i][j];//C(i,i-j)=C(i,j)
        }
    }
}

【PAT】2. 数学问题