【OJ】 : 容斥原理计算出 1< =n <…

2018-06-18 03:53:57来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

  

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

 

问题描述:


  有个1到n的数列,数一下其中能够被 2,3,5 整除的数字的个数。例如当n = 6 的时候有 23456.这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就出计算结果。

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:红黑树

下一篇:Linux进程间通信(System V) --- 信号量