算法基础之能被整除的数

2024-01-01 18:44:22

能被整除的数

  • 核心思想: 容斥原理

    • 总面积 = 1-2+3-4….

    • 总集合元素中个数 = 1-2+3-4….

    • 在这里插入图片描述

    •   #include<iostream>
        #include<cstring>
        #include<algorithm>
        
        using namespace std;
        const int N = 20;
        typedef long long LL;
        
        int p[N];
        
        int main()
        {
            int n,m;
            cin>>n>>m;
            
            for(int i=0;i<m;i++) cin>>p[i];  //输入质数
            
            int res = 0;
            for(int i=1;i< 1 << m ;i++)  //用二进制数表示一张图 遍历所有取法
            {
                int t = 1 , cnt = 0;  //t为所有质数乘积 cnt为集合个数
                for(int j =0;j<m;j++)  //遍历图中每一位数
                {
                    if(i >> j & 1)  //若取到j集合
                    {
                        if((LL)t * p[j] > n)  //该取法失效
                        {
                            t = -1;
                            break;
                        }
                        t *= p[j];  //t为所有质数乘积
                        cnt++;  //集合个数++
                    }
                }
                if(t != -1)  //取法有效
                {
                    // n/t 为 该集合个数(不能整除 向下取整)
                    if(cnt % 2) res += n/t;  //集合个数为奇数 +
                    else res -= n/t;  //集合个数为偶数 -
                }
            }
            
            cout<<res;
        }
      

文章来源:https://blog.csdn.net/Pisasama/article/details/135326745
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。