大水题

[编程题]大水题

热度指数：2359 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出一个数n，求1到n中，有多少个数不是2 5 11 13的倍数。

输入描述:

本题有多组输入
每行一个数n，1<=n<=10^18.

输出描述:

每行输出输出不是2 5 11 13的倍数的数共有多少。

示例1

输入

输出

说明

1 3 7 9

算法知识视频讲解

白给怪

发表于 2020-07-15 19:26:51

比较简单的容斥原理的题目下面贴两张概念性的图片很容易理解话不多说就贴代码啦： #include<iostream> #include<algorithm> #include<set> #include<string> #include<cstr 展开全文

平凡的小白

发表于 2020-09-12 13:43:32

#include<bits/stdc++.h> using namespace std; typedef long long ll; ll a[5]={0,2,5,11,13}; int main() { ll n; while(cin>>n) { 展开全文

东溪看水

发表于 2020-06-30 14:31:34

题目给出一个数 n，求 1 到 n 中，有多少个数不是 2、5、11、13 的倍数。解题思路根据容斥原理，先不考虑重叠的情况，把 2、5、11、13 的所有倍数的数目先计算出来，然后再把计数时重复计算的数目排斥出去。所以，1 到 n 中，这四个数的倍数的总数为cnt = n/2 + n/5 + 展开全文

咔cat

发表于 2024-03-29 10:56:45

没什么好说的，附上容斥原理的公式吧百度百科：https://baike.baidu.com/item/%E5%AE%B9%E6%96%A5%E5%8E%9F%E7%90%86/10146840?fr=ge_ala #include<bits/stdc++.h> using names 展开全文

昵称很长很长真是太好了

发表于 2020-07-17 16:03:10

题解：容斥原理要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回有三个集合相交的部分，再减去所有四个集合相交的部分....依此类推，一直计算到所有集合相交的部分。拿这个题举个栗子。你先计算出单个数被整除的次数加起来，你会发现比如说10这个数字，会被展开全文