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:
- 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.
- 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;
}
bign Add(bign a, bign b){
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;
}