数学相关知识

1.质数

  定义:若一个正整数除了1和他自身外无法被其他自然数整除,该数则称为质数(又名素数),否则称为合数(又名合成数).  注意:1不是质数也不是合数

  质数的判定: 如果在2~√n 内的整数能找到整除n的整数,则该数为合数,否则为质数.

       质数的筛选:根据素数的倍数不是素数的原理,每次遍历到素数,其倍数都被标记为合数.根据这个原理便可以得到一定量的素数

利用埃氏筛(O(nlognlogn))可获得

//埃氏筛
const int maxn = 1e6 + 10;
int prime[maxn], primesize;
int vis[maxn];
void Prime(int n)//判断1~n内的素数的个数primesize并记录在prime内
{
	memset(prime, 0, sizeof(prime));
	memset(vis, 0, sizeof(vis));
	for (int i = 2; i <= n; i++)
	{
		if (!vis[i])
		{
			prime[++primesize] = i;
		}
		for (int j = i; j <= n / i; j++)
		{
			vis[j*i] = 1;
		}
	}
}

_____________________________________________________________________________

也可以利用线性筛/欧拉筛(O(n))获得

//欧拉筛
int prime[maxn], primesize;
int vis[maxn];
void Prime(int n)
{
	memset(prime, 0, sizeof(prime));
	memset(vis, 0, sizeof(vis));
	for (int i = 2; i <= n; i++)
	{
		if (!vis[i])
		{
			prime[++primesize] = i;
		}
		for (int j = 1; i <= n / prime[j] && j <= primesize; j++)
		{
			vis[i*prime[j]] = 1;
			if (i%prime[j] == 0)
			{
				break;
			}
		}
	}
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

2.质因数分解

  定义:任何一个大于1的正整数都能唯一分解为有限个质数的乘积.可写成

N=p1^a1 * p2^a2 * p3^ a3 * .......pk^ak.  其中p都是素数,a是p的指数.

  跟据质数的判定以及质数的筛选,我们可以用代码得到一个数所含有的质因子的情况

//求单个数的质因数情况
const int maxn = 1e6;
int p[maxn], c[maxn];//p记录质因子  c记录质因子的指数值
void divide(int n)
{
	int m = 0;
	for (int i = 2; i <= sqrt(n); i++)
	{
		if (n%i == 0)//i是质数
		{
			p[++m] = i, c[m] = 0;
			while (n%i == 0)n /= i, c[m]++;//除掉所有的i
		}
	}
	if (n > 1)//n是质数
	{
		p[++m] = n, c[m] = 1;
	}
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

3.约数

  定义:若整数n除以d的余数为0,既d能整除n,则称d是n的约数,n是d的倍数,记为d|n.

  算术基本定理的推论:若正整数N被唯一分解为N=p1^a1 * p2^a2 * p3^a3 *.......pk^ak 其中pi都是质数 ai都是正整数 ,则

  N的正约数的个数为:

            (a1 +1)*(a2+1)*(a3+1)*........*(ak+1);

  N的所有正约数的和为: 

            (1+p1+p1^2+.......+p1^a1)*.......*(1+pk+pk^2+.......+pk^ak)

 求1~N每个数的正约束集合----倍数法(O(nlogn))

对于每个数d,1~N中以d为约束的数就是d的倍数d,2d,3d...

//倍数法
const int maxn = 5e5 + 10;
//
vector<int> factor[maxn];
void fact(int n)
{
	for (int i = 1; i <= n; i++)//以i为约数的数有
	{
		for (int j = 1; j <= n / i; j++)
		{
			factor[i*j].push_back(i);//加入其中
		}
	}
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

4.最大公约数

  能同时整除自然数a与自然数b的最大自然数c

//欧几里得算法
int gcd(int a, int b)//求最大公约数
{
	return b == 0 ? a : gcd(b, a%b);
}

上一篇:一道博弈题


下一篇:Codeforces Round #736 (Div. 2) A题题解