算数基本定理

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

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

数学公式描述

N=P1^r1 * P2^r2 *P3^r3*...*Pn^rn  (P1<P2<P3<...<PN & Pi 是质数 & ri>=0)

 

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

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)

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)

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);