手撕大厂笔试之数学全家桶_大厂 笔试 组合数学

目录

个人介绍

本博客的概况

因数

考法

朴素解法

优化做法

例题 ​

筛质数

前言：

原理：

引入的知识：

具体的阐述：

代码模板：

难点的解释：

例题：

 最大公约数

代码模板：

万能的stl：

欧几里德定理

内容

例题​

快速幂（a^b）

原理：

代码模板：

数论分块：

用处：

相关推导：

代码模板： 

例题：

---

个人介绍

各位CSDN的友友们，大家好，我是小熙，一个算法小透明，希望在CSDN的大舞台可以和大家一起取得进步（^_^）

个人现状：上个学期在学校的ACM小组学了一个学期的算法，但是世界很大，我的梦想很远，我希望在我年轻的时候可以走出国门，到世界的其他地方看一看，再加上我的算法功底可能真的不太足以支持我在ACM比赛上做出成绩。所以我选择逐渐淡出ACM小组，并把之前的知识整理成博客供大家分享。

学习算法的小方法：知道算法的基本原理——>知道代码实现——>总结出代码模板并熟练于心——>基本模板题——>变式思维题

本博客的概况

本章节将从因数，约数，筛质数，欧几里得，快速幂，数论分块几大角度展开。

因数

考法

考法一：通常题干中会要求我们来求某一个数据的因数的个数

考法二：【1，n】（n/i）就是【1，n】的范围内i作为约数的次数——当你看到下面的数论分块你就知道这个性质的厉害了。

朴素解法

原理：一个数一个数地去统计它的约数的个数

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int d[N];//d[i]表示的就是数字i的因数的个数
int main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			if(i%j==0)
			{
				d[i]++;
			}
		}
	}
	cout<<d[3];
}

缺点：时间复杂度不够优秀

优化做法

 原理：用倍数反过去推导因数。比如要求出8的因数的个数，朴素的做法是枚举1~7看是否可以被8整除，但是优化的做法是用2,4,8这些因数去推导它的倍数。

 时间复杂度：n*ln(n)

 解释：可能有人觉得奇怪吧，不是n^2的复杂度吗，嘿嘿，其实有严格的证明的，当当当当！！！下面的就是

 代码模板

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int d[N];
int n;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)//i在某种意义上表示的是因数
	{
		for(int j=i;j<=n;j+=i)//j表示的就是由i枚举对的倍数
		{
			d[j]++;
		}
	}
	cout<<d[3];
}
 
​

例题

 

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int mod=1e9+7;
typedef long long ll;
ll ans;
int d[N];
int main()
{
	int n;cin>>n;
	for(int i=1;i<=N;i++)
	{
		for(int j=i;j<=N;j+=i)
		{
			d[j]++;
		}
	}
	for(int i=1;i<=n;i++)
	{
	  ans=(ans+d[i])%mod;	
	}
	cout<<ans;
	return 0;
}

筛质数

前言：

对于初学者来讲，只要理解了欧拉筛，那么埃氏筛，朴素筛法。其实吧，与其讲是筛质数，不如讲是筛合数，把合数踢出来，余下的就是质数了。

原理：

引入的知识：

唯一分解定理：任何一个大于1的自然数 N,如果N不为质数，**那么N可以唯一分解成有限个质数的乘积。比如12可以分解为2,2,3的乘积，8可以分解为2,2,2的乘积。

具体的阐述：

由于一个数可以被分解为若干个质数的乘积，那么欧拉筛的精髓就在于它保障了每个被筛出来的合数是被它的最小因数和另一个因数的乘积筛掉的。关键词“最小因数”

代码模板：

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int cnt;
int p[N];//存储质数的数组
bool vis[N];//vis[i]判断的是i是否为质量，为1的话为合数，为0的话为质数
void ola(int n)
{
	for(int i=2;i<=n;i++)
	{
		if(vis[i]==0) p[++cnt]=i;
		for(int j=1;j<=cnt&&i*p[j]<=n;j++)
		{
			vis[i*p[j]]=1;
			if(i%p[j]==0) break;//这一步也是许多人看不懂的，但他就是保障筛掉的合数是最小质数和令一个因数筛出的关键步骤
		}
	}
}
 
int main()
{
	int n;
	cin>>n;
	ola(n);
	cout<<cnt<<endl;
	cout<<p[2]<<endl;
	return 0;
}

难点的解释：

（1）：关于模板中的两层循环：筛出合数的方式可以理解为"c=a*b"的方式来筛出的，第二层p[j]可以理解为筛出质数的最小质数a，第一层i可以理解为筛的是因数b。 

（2）：关于步骤“if (i%p[j]==0) break”：如果没有这一个步骤的话，以12为例，12就会被3*4和2*6重复筛掉，而加了这一步就可以保障在即将被3*4筛掉的时候，由于4可以被p[1]即2整除，提前阻止重复筛的现象，达到最优的时间复杂度。

例题：

P3912 素数个数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int cnt;
int p[N];//存储质数的数组
bool vis[N];//vis[i]判断的是i是否为质量，为1的话为合数，为0的话为质数
void ola(int n)
{
	for(int i=2;i<=n;i++)
	{
		if(vis[i]==0) p[++cnt]=i;
		for(int j=1;j<=cnt&&i*p[j]<=n;j++)
		{
			vis[i*p[j]]=1;
			if(i%p[j]==0) break;//这一步也是许多人看不懂的，但他就是保障筛掉的合数是最小质数和令一个因数筛出的关键步骤
		}
	}
}
 
int main()
{
	int n;
	cin>>n;
	ola(n);
	cout<<cnt<<endl;
	return 0;
}

最大公约数

代码模板：

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

万能的stl：

__gcd(a,b)函数非常方便，但要小心的是stl用多了可能会TLE，因为电脑从若干封装好的函数中找到__gcd(a,b)还是有点小耗时间的。

欧几里得定理

内容

内容：对于不完全为 0 的整数 a，b，gcd（a，b）表示 a，b 的最大公约数。那么一定存在整数 x，y 使得 gcd（a，b）=ax+by。

是不是有点晦涩难懂，明白但不知道写题的时候怎么样。嘿嘿，请看下面的例题。

例题

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int dp[N];//dp[i]表示的是i个包子可否凑出
int w[N];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>w[i];
	dp[0]=1;
	
	int temp=1;
	for(int i=1;i<=n;i++)
	{
		temp=__gcd(temp,w[i]);//这里偷懒用来stl,啊哈哈哈
	}
	
	if(temp!=1){
		cout<<"INF"<<endl;//欧几里得的体现
		return 0;
	}
	
	for(int i=1;i<=n;i++)
	{
	for(int j=0;j<N;j++)
	{
		if(dp[j]==1)
		{
			dp[j+w[i]]=1;
		}
	}
   }
   int ans=0;
   for(int i=1;i<N;i++) if(dp[i]==0) ans++;
   
   cout<<ans;
   return 0;
}

总结：之前没有把欧几里得的用法讲明白这里可以理解为给你一个数集（a,b,c,d,......）,用x*a+y*b+z*c.....来凑数（x,y,z均为常数），假如这个数集的最大公约数为1，那么它不能凑出来的数据是有限的，如果这个数集的最大公约数不为1，那么它不能凑出来的数无限的。

快速幂（a^b）

原理：

原理：原来求取a^b总是a*a*a*a.........*a*a一个又一个地去乘，这样时间复杂度太大了。如果转化为下图中的二进制求法，会快许多。

 就是把指数b看做是一个二进制数，然后利用二进制的操作符来算a^b。b从右向左边数的第一位就是a，第二位就是a^2,第三位就是a^4.....以此类推

补充的知识：

（1）：b&1:判断二进制数据b的最后一位是0还是1，如果（(a&1)==1）的话就是1,（(a&1)==0)的话就是0。

（2）：b>>=1:表示二进制数b向右移动一位，例如b=1000001进行了b>>=1以后就是100000

总结：上面这两个工具可以判断一个数据变为二进制以后每一位是0是1的情况

代码模板：

#include<bits/stdc++.h>
using namespace std;
int quick_pow(int a,int b)//快速幂
{
	int ans=1;int temp=a;
	while(b)
	{
		if(b&1)ans=ans*temp;
		temp=temp*temp;
		b>>=1;
	}
	return ans;
}
 
int main()
{
	int a,b;cin>>a>>b;
	int result=quick_pow(a,b);
	cout<<result;
	return 0;
}

数论分块：

用处：

用处：主要是用整体分块的思想快速计算含有（n/i）的向下取整类型的求和式子的值，一个一个算太慢了

 做题的时候一些数学题假如含有%或者取模就应该要想到数论分块，来，看下边的例题

相关推导：

代码模板： 

for(ll l=1,r;l<=n;l=r+1) 
{
	r=n/(n/i); 
    ans+=(n/i)*(r-i+1); 
 } 

例题：

P1403 [AHOI2005]约数研究 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ll ans=0;ll n;
	cin>>n;
	for(ll l=1,r;l<=n;l=r+1)//这里基本就是上面的死的模板了
	{
		r=n/(n/l);
		ans+=(r-l+1)*(n/l);
	}
	cout<<ans<<endl;
}

分析：这里要求1~n因数个数的和，嘿嘿，记起开始我们提到的性质——(n/i）就是【1，n】的范围内i作为约数的次数。所以比如想要求（1~3）之间所有数据的约数个数之和，那么先统计（1~3）之间1出现的次数，（1~3）之间2出现的次数，（1~3)之间3出现的次数。3+1+1==5次。直接转化为问题了。然后套模板走人。