频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
Hdu 1796 How many integers can you find (数学_容斥原理)
2012-08-05 11:04:00      个评论      
收藏   我要投稿

题目大意:给定n和一个大小为m的集合,集合元素为非负整数。为1...n内能被集合里任意一个数整除的数字个数。n<=2^31,m<=10

解题思路:容斥原理地简单应用。先找出1...n内能被集合中任意一个元素整除的个数,再减去能被集合中任意两个整除的个数,即能被它们两只的最小公倍数整除的个数,因为这部分被计算了两次,然后又加上三个时候的个数,然后又减去四个时候的倍数...这题很多人通过深搜来进行,我懒得写深搜,直接枚举状态0...(1<<m),然后判断状态内涵几个集合元素,然后计算lcm和能被整除的个数,最后判断下集合元素的个数为奇还是偶,奇加偶减。
     这题有个地方很无聊,集合里面会混进0,0混进来要先删掉它才不至于在求gcd,lcm的时候RE,0本身对结果没什么影响。

测试数据:
12 2
2 3

12 3
1 2 3

12 4
1 2 3 0

OutPut
7
11
11

C艹代码:
[cpp] 
#include <stdio.h> 
#include <string.h> 
 
 
int ans,n,m; 
int arr[200],cnt; 
int select[200],Lcm; 
 
 
int gcd(int n,int m) { 
 
    int r = n % m; 
    while (r) { 
 
        n = m,m = r; 
        r = n % m; 
    } 
    return m; 

int lcm(int n,int m) { 
 
    return n / gcd(n,m) * m; 

int Solve(int n) { 
 
    int i,j,k; 
 
 
    for (ans = 0, i = 1; i < (1<<m); ++i) { 
 
        cnt = 0; 
        for (j = 0; j < m; ++j) 
            if (i & (1<<j)) select[++cnt] = j; 
         
 
        for (Lcm = j = 1; j <= cnt; ++j)  
            Lcm = lcm(Lcm,arr[select[j]]); 
 
 
        if (cnt % 2 == 1)  ans += n / Lcm; 
        else ans -= n / Lcm; 
    } 
    return ans; 

 
 
 
int main() 

    int i,j,k; www.2cto.com
 
 
    while (scanf("%d%d",&n,&m) != EOF) { 
 
        for (i = 0; i < m; ++i) { 
         
            scanf("%d",&arr[i]); 
            if (arr[i] == 0) i--,m--; 
        } 
        printf("%d\n",Solve(n-1)); 
    } 


作者:woshi250hua
点击复制链接 与好友分享!回本站首页
相关TAG标签 原理 数学 容斥
上一篇:hdu2047阿牛的EOF牛肉串
下一篇:Zoj 3527 Shinryaku! Kero Musume (DP_章鱼图上的树形DP)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站