项目管理系统平台_百度seo最新算法_网站建设包括哪些内容_seo企业推广案例

一：质数

1：判断是否是质数——试除法：

bool isprimer(int n)
{if (n<2){return false;}for (int i=2; i<=n/i; i++)//优化后只枚举到根号n;{if (n%i==0){return false;}}return true;
}

2：质数筛——求1-n中质数的个数

可以使用预处理的方法，将1-n中所有的质数预先存到一个数组中。

P3383 【模板】线性筛素数 - 洛谷

const int N=100000005;
int primer[N],cnt;
bool st[N];
void get_primers(int n)
{for (int i=2; i<=n; i++){if (!st[i]) primer[cnt++]=i;for (int j=0;primer[j]<=n/i;j++){st[primer[j]*i]=true;//将质数的所有倍数都筛掉if (i%primer[j]==0) break;}}
}

二、约数

1：求一个数的所有约数——同样是试除法

P1403 [AHOI2005] 约数研究 - 洛谷（没ac版）

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);}}return res.size();
}

2：辗转相除法求最大公约数——gcd

P1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题 - 洛谷

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

三、快速幂算法

快速求出a的k次方mod p的结果

int qmi(int a,int k,int p)
{int res=1;while(k){if (k&1){res=(ll)res*a%p;}k>>=1;a=(ll)a*a;}return res;
}

四、求组合数

就是我们高中常求的C几几。

P2822 [NOIP 2016 提高组] 组合数问题 - 洛谷

同样运用了预处理的思想，先将1-n的所有组合可能求出来，放到数组里

int c[N][N];void init(int k)
{for (int i=0; i<N;i++){for (int j=0; j<=i; j++){if (!j){c[i][j]=1;}else{c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;}}}
}