算数基本定理 + 容斥定理

算数基本定理

定义:任何一个大于1的自然数,如果N不为质数,那么N可以分解成有限个质数的乘积,并且在不计次序的情况下,这种分解方式是唯一的。

例如:60可以分解为 2^2 * 3 * 5

数学公式描述

N=P1^r1 * P2^r2 * P3^r3 * … * Pn^rn (P1<P2<P3<…=0)

质因子分解计算方法 算法复杂度 ( O(√n) )

1
2
3
4
5
6
7
8
9
10
11
12
map<int,int> prime_factor(int n){
map<int,int>ans;
for(int i=2;i*i<n;i++){
while(n%i==0){
++ans[i];
n/=i;
}
}
if(n!=1)
ans[n]=1;
return ans;
}

算数基本定理的应用

如何求N有几个因子?

根据算数基本定理:N=P1^r1 * P2^r2 * P3^r3 * … * Pn^rn

根据排列组合得到结果:

ans=(1+r1) * (1+r2) * (1+r3) * … * (1+rn)

如何求N的所有因子之和?

根据算数基本定理:N=P1^r1 * P2^r2 * P3^r3 * … * Pn^rn

求GCD(X,Y)和LCM(X,Y)

根据算数基本定理:

X=P1^x1 * P2^x2 * P3^x3 * … * Pn^xn

Y=P1^y1 * P2^y2 * P3^y3 *… * Pn^yn

根据GCD和LCM的定义

容斥定理

要计算几个集合并集的大小,我们要先将所有单个集合的大小计算出来,然后减去所有两个集合相交的部分,再加回所有三个集合相交的部分,再减去所有四个集合相交的部分, 依此类推,一直计算到所有集合相交的部分。

用Venn图来表示

数学公式描述

如果要对n个物体进行选择,那么有多少种情况?

代码复杂度为O(2^n)

1
2
3
4
5
6
for(int i=0;i<(1 << m);i++){
for(int j=0;j<n;j++){
printf("%d",i>>j & 1);
}
puts("");
}

容斥定理的应用

问题:魔镜给小明m个数字(a1、a2 …… am)和一个整数n,魔镜定义:如果有一个数,是这m个数字里面任意一 个数的倍数,那么这个数称为LuckyNumber。而小明会的题数为[1,n]闭区间内LuckyNumber的数量。 (0 < m < 15) 那么请你帮小明计算一下他会的题目数。

代码 复杂度为O(2^n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LL ans=0;
for(int i=1; i<(i<<m);i++){
int cnt=0;
LL LCM=1;
for(int j=0;j<m;j++){
if(1&(i>>j)){//按位运算判断第m个数是否使用
cnt++;
LCM=lcm(LCM,a[j]);
}
}
if(cnt&1) ans+=n/LCM;//判断n中元素使用的个数,奇加偶减
else ans-=n/LCM;
}

printf("%lld\n",ans);
感谢您的支持
-------------本文结束感谢您的阅读-------------