算数基本定理

定义：任何一个大于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);