OJ : 容斥原理计算出 1< =n < 1e9 中是2,3,5倍数的整数的数量

　　

　　最近ACM时遇到个题，题意如下、

 

问题描述:

---

　　有个1到n的数列，数一下其中能够被 2，3，5 整除的数字的个数。例如当n = 6 的时候有 2，3，4，5，6.这5个数满足条件，所以我们应该输出 5 。

 

 

 

输入

---

    多组输入到文件尾，每组输入一个 n (n < 1e9)

 

输出

---

    输出对应的个数

 

样例输入

---

1
     2
     6

 

样例输出

---

0
     1
     5

 

　　一眼看上去，很简单呀，想都没想就写上了以下代码

 

#include <stdio.h>
long long main(void)
{
    long long n, i, flag = 0;
    while(scanf("%lld", &n))
    {
      for(i = 1; i <= n; i ++)
        if(i % 2 == 0 || i % 3 == 0 || i % 5 == 0)
        flag ++;
        printf("%lld\n", flag);
        flag = 0;
    }
}

 

 

 

　　一提交 时间超限 ,我就在本地编译器上调试了一下，看了一下题目 (n < 1e9) 便输入 99999999 结果半天没有计算出结果，这肯定超时啦，题目限定时间为 1000 ms 时间不超限就怪了。

　　既然这样不行，那就要优化算法，思来想去也没有什么头绪。后来看到了这篇博客 http://blog.csdn.net/u010885899/article/details/48022633 文章内容就讲的是利用容斥原理计算出 1<=N 中是 2、3、5、7 倍数的整数的数量。

　　受此启发，百度百科了一下 容斥原理 :

　　在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。

　　如果被计数的事物有A、B、C三类，那么，A类和B类和C类元素个数总和= A类元素个数+ B类元素个数+C类元素个数—既是A类又是B类的元素个数—既是A类又是C类的元素个数—既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数。（A∪B∪C = A+B+C - A∩B - B∩C - C∩A + A∩B∩C）

　　由此定义，可以照着葫芦画瓢了。

　　能被 2 整除的事件记为 A 类， 能被 3 整除的事件记为 B 类， 能被 5 整除的事件记为 C 类。 那能被 2 3 5 整除的整数数量可以这样表示: A 类元素个数 + B 类元素个数 + C 类元素个数 — 既是 A 类又是 B 类元素的个数 — 既是 B 类又是 C 类元素的个数 — 既是 A 类又是 B 类元素的个数 + 既是 A 类 又是 B类而且是 C 类元素的个数 （即 能被 2 或 3 或 5 整除的个数 = 能被 2 整除的个数 + 能被 3 整除的个数 + 能被 5 整除的个数 — 能同时被 2 3 整除的个数 — 能同时被 2 5 整除的个数 — 能同时被 3 5 整除的个数 + 能同时被 2 3 5 整除的个数）

　那么就可以写出对应代码

#include <stdio.h>
int main(void)
{
    int n, num;
    int a, b, c;
    int ab, ac, bc;
    int abc;
    while(scanf("%d", &n))
    {
        a = n / 2;
        b = n / 3;
        c = n / 5;

        ab = n / (2 * 3);
        ac = n / (2 * 5);
        bc = n / (3 * 5);

        abc = n / (2 * 3 * 5);

        num = a + b + c - ab - ac - bc + abc;
        printf("%d\n", num);
    }
}

 

 

 

 　　提交， Bingo 没问题，本地也测试了一下输入稍微大于 1 e 9 的数也是不到 1000 ms就出计算结果。