数学知识学习1

1、数论

        1质数判定  i<=n/i优化O(sqrt(n)) 

bool is_prime(int n){if(n<2)return false;for(int i=2;i<=n/i;i++){if(n%i==0)return false;} true;
}

        分解质因数 i<=n/i优化O(sqrt(n))

// 定义一个函数 divide，接收一个整数 n 作为参数，用于分解质因数
void divide(int n){// 使用一个循环从2开始遍历到sqrt(n)（即n/i，因为一个// 大于sqrt(n)的因数必定和一个小于或等于sqrt(n)的因数成对出现）for(int i=2;i<=n/i;i++){// 如果 n 能被 i 整除，说明 i 是 n 的一个因数if(n%i==0){int s=0; // 定义一个计数器 s，用于记录当前因数 i 的个数// 使用一个内层循环，持续除以当前的因数 i，直到 n 不能被 i 整除为止while(n%i==0){n/=i; // 将 n 除以当前的因数 is++;  // 计数器 s 自增，记录当前因数 i 的个数}// 输出当前的因数 i 和它的个数 scout<<i<<" "<<s<<endl;}}// 循环结束后，如果 n 大于 1，说明 n 本身就是一个质数，并且是 n 的一个因数if(n>1)cout<<n<<" "<<1<<endl; // 输出 n 本身作为质因数，个数为 1
}

 埃氏筛法：一个数P中的1到P-1中的质数不是P的因数P就是质因数

 欧式筛法：n只会被最小质因子筛掉。

int primes[N],cnt;
bool st[N]; 
void get_primes(int n){//埃氏筛法 O(nloglogn)for(int i=2;i<=n;i++){if(!st[i]){primes[cnt++]=i;for(int j=i+i;j<=n;j+=i)st[j]=true;}}
} 
void get_primes(int n){//欧式筛法 for(int i=2;i<=n;i++){if(!st[i])primes[cnt++]=i;for(int j=0;primes[j]<=n/i;j++){从小到大枚举质数st[primes[j]*i]=true;//用最小质因子数把倍数筛掉if(i%primes[j]==0)break;//prime[j]一定是i的最小质因子 //i%pj==0时pj一定是i的最小质因子,pj一定是pj*i的最小质因子//i%pj!=0时pj一定小于i的所有质因子,pj也一定是pj*i的最小质因子//对于一个合数x，假设pj是x的最小质因子，当i枚举到x/pj时都会筛掉 //每一个数都有一个最小质因子,都只会被筛一次，所以是线性的 } }
}

   2约数(1)试除法求约数O(sqrt(n))

vector<int>get_divisors(int n){vector<int>res;for(int i=1;i<=n/i;i++){if(n%i==0){res.push_back(i);if(i!=n/i)res.push_back(n/i);}}sort(res.begin(),res.end());return res;
} 

            (2)约数个数

任何一个整数n因式分解后N=p1^a1×p2^a2×......pk^ak那么约数个数为(a1+1)(a2+1)......(ak+1) 

任何一个整数n的约数d=p1^b1×p2^b2×......pk^bk（0<=bi<=ai）所以每一个bi就有ai+1种

#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int main() {int n;cin >> n;unordered_map<int, int> primes;//定义一个无序映射 primes，用于存储质因数及其出现的次数while (n--) {int x;cin >> x;for (int i = 2; i <= x / i; i++) {while (x % i == 0) { // 如果 i 是 x 的一个质因数x /= i; // 将 x 除以 i，去除这个质因数primes[i]++; // 在 primes 中增加质因数 i 的计数}}// 循环结束后，如果 x 大于 1，那么 x 必然是一个质数（且之前没有被完全除尽）if (x > 1) primes[x]++; // 在 primes 中增加这个质因数的计数}LL res = 1;// 遍历 primes 中的每个质因数及其计数for (auto prime : primes) res = res * (prime.second + 1) % mod;cout << res << endl;return 0;
}

            (3)约数之和

约数之和为(p1^0+p1^1+......+p1^k)×(p2^0+p2^1+......+p2^k)×......(pk^0+pk^1+......+pk^k)排列组合

#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
int main(){int n;cin>>n;unordered_map<int,int>primes;whlie(n--){int x;cin>>x;for(int i=2;i<=x/i;i++){while(x%i==0){x/=i;primes[i]++;}}if(x>1)primes[x]++;}LL res=1;for(auto prime:primes){int p=prime.first,a=prime.second;//底数和指数LL t=1;whlie(a--)t=(t*p+1)%mod;res=res*t%mod; }cout<<res<<endl;return 0;
}

            （4）欧几里得算法（辗转相除法）求最大公约数

                性质：d/a  d/b--->d/(ax+by)   

                原理：a和b的最大公约数==b和a模b的最大公约数

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