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

2018-02-05 20:23:48来源:cnblogs.com作者:notfound945人点击

分享

  

  最近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就出计算结果。

相关文章

    无相关信息

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台