# [PAT grade a review] topic review 9: mathematics related

## Topic review 9 (9.10): mathematics related

### 1 maximum common divisor and minimum common multiple

Code of maximum common divisor:

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

lcm(a,b) = a / gcd(a,b) * b;	//Least common multiple
```

### 2 representation of scores

Extra attention should be paid to division. If the read divisor is 0, it needs to be output directly.

```struct Fraction{
int up, down;
};

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), abs(result.down));
result.up /= d;
result.down /= d;
}
return result;
}
```

### 3 prime

#### 3.1 judging prime

```bool isPrime(int n){
if(n <= 1) return false;
int sqr = (int)sqrt(1.0* n);
for(int i=2; i<=sqr; i++){
if(n % 2 == 0) return false;
}
return true;
}
```

#### 3.2 prime table obtained by sieve method

```const int MAXN = 101;   //Table length
int prime[MAXN], pNum = 0;  //Prime stores all prime numbers, pNum stores the number of prime numbers
bool notPrime[MAXN] = {0};  //The initial assumptions are prime numbers
void Find_Prime(){
for(int i=2; i<MAXN; i++){
if(notPrime[i] == false){
prime[pNum++] = i;
for(int j = i+i; j<MAXN; j += i){
notPrime[j] = true;
}
}
}
}
```

### 4 prime factor decomposition

Since 1 itself is not a prime number, it has no prime factor. Since each quality factor can appear more than once, a structure factor can be defined to store the quality factor and its number.

Idea of qualitative factor decomposition:

1. Enumerate all prime factors P in the range of 1~sqrt(n) to judge whether P is a factor of n. If yes, add the prime factor p to the fac array and initialize its number to 0. Then, as long as P is still a factor of N, let n divide P continuously, and add one to the number of P each time; If not directly skip.
2. If n is still greater than 1 after the above steps, it indicates that there is a prime factor greater than sqrt(n) (possibly n itself). At this time, you only need to add the remaining N to the fac array and set its number to 1.
```struct factor{
int x, cnt;
}fac[10];

int num = 0;
int sqr = sqrt(1.0 * 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){
n /= prime[i];
fac[num].cnt++;
}
num++;
}
if(n == 1) break;
}
if(n != 1){
fac[num].x = n;
fac[num++].cnt = 1;
}
```

If the number of factors of a positive integer N is required, only the prime factor decomposition is needed to obtain that the pi of each prime factor is e1,e2,e3... ek respectively, then the number of factors of N is (e1 + 1)*(e2 + 1)

### 5 large integer operations

High precision A + B

```struct bign{
int d[1000];
int len;
bign(){
fill(d, d+1000, 0);
len = 0;
}
};

bign change(string str){
bign a;
a.len = str.size();
for(int i=0; i<a.len; i++){
a.d[i] = str[a.len - i - 1] - '0';
}
return a;
}

int carry = 0;
bign c;
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;
}

void printBign(bign a){
for(int i=a.len-1; i>=0; i--){
printf("%d",a.d[i]);
}
}
```

High precision A - B, first compare the size of A and B, if A is smaller than B, exchange A and B, and add A negative sign after calculating the result.

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

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 >= 2 && c.d[c.len - 1] == 0){
c.len--;
}
return c;
}

```

High precision A × Low precision B:

```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 = carry / 10;
}
return c;
}
```

High precision A ÷ low precision B:

```bign divide(bign a, int b, int &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 >= 2 && c.d[c.len - 1] == 0){
c.len--;
}
return c;
}
```

### 6 combination number

#### 6.1 find n! How many qualitative factors are there in p

O(logN): cal(n,5) is n! Number of last 0.

```int cal(int n, int p){
int ans = 0;
while(n){
ans += n / p;
n /= p;
}
return ans;
}
```

#### 6.2 calculation of combination number

Recursive computation, complexity O(n2);

```long long res[67][67] = {0};
long long C(long long n, long long m){
if(m == 0 || n == m) return 1;
if(res[n][m] != 0) return res[n][m];
return res[n][m] = C(n-1, m) + C(n-1, m-1);
}
```

Define deformation calculation, complexity 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;
}
```

Calculate C(n,m)%p. assuming that twice P will not exceed int, it can support the 9th power of M < = n < = 1000 and P < = 10

```int res[1010][1010] = {0};
int C(int n, int m){
if(m == 0 || n == m) 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;
}
```

If you want to support long long level m, n, use lucas algorithm

```int Lucas(int n, int m){
if(m == 0) return 1;
return C(n%p, m%p) * Lucas(n/p, m/p) % p;
}
```

Keywords: C Algorithm data structure PAT

Added by Naki-BoT on Sun, 19 Sep 2021 14:23:01 +0300