51nod 1284:2 3 5 7的倍数 容斥原理
2024-08-29 06:39:56
基准时间限制:1 秒 空间限制:131072 KB 分值: 5 难度:1级算法题
收藏
关注
给出一个数N,求1至N中,有多少个数不是2 3 5 7的倍数。 例如N = 10,只有1不是2 3 5 7的倍数。
Input
输入1个数N(1 <= N <= 10^18)。
Output
输出不是2 3 5 7的倍数的数共有多少。
Input示例
10
Output示例
1
容斥原理的描述如下:
要计算几个集合并集的大小,我们要先将单个集合的大小计算出来,然后减去两个集合相交的部分,再加回三个集合相交的部分,再减去四个集合相交的部分,以此类推,一直计算到所有集合相交的部分。
所以这个题目要求的是不是2 3 5 7的倍数,可以求是2 3 5 7的倍数之后,再减去即可。
这样就会用到容斥原理,先求仅仅只是整除2 3 5 7的数量,再减去整除了它们之间两两的乘积的数量,再加上整除它们三个之间的乘积的数量,再加上整除四个的数量。
而这个数量也很有意思,1到num中整除c的数量正是num/c的值。
所以,代码:
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#pragma warning(disable:4996)
using namespace std; long long n,num,a,b,c,d,ab,ac,ad,bc,bd,cd,abc,abd,bcd,acd,abcd; int main()
{
cin>>n; num=0; a=n/2;
b=n/3;
c=n/5;
d=n/7; ab=n/6;
ac=n/10;
ad=n/14;
bc=n/15;
bd=n/21;
cd=n/35; abc=n/30;
abd=n/42;
acd=n/70;
bcd=n/105; abcd=n/210; num=a+b+c+d-ab-ac-ad-bc-bd-cd+abc+abd+acd+bcd-abcd; cout<<n-num<<endl;
return 0;
}
版权声明:本文为博主原创文章,未经博主允许不得转载。
最新文章
- php基础知识
- 解除Team Foundation Server 5个用户的限制
- Centos6 安装 Redis
- Confluent Platform 3.0支持使用Kafka Streams实现实时的数据处理(最新版已经是3.1了,支持kafka0.10了)
- 苹果Mac OS X显示隐藏文件的方法
- ios 消息推送流程 转载
- Redis经验谈
- screen命令学习
- Xstream 学习地址
- (转)java读取数据库表信息,子段
- 答读者问(8):相关Java问题涉及到学习
- (转)NoSQL——Redis在win7下安装配置的学习一
- android webview处理下载内容
- xshell安装运行时提示缺少mfc110.dll
- js实现活动倒计时
- IIS Express ArgumentOutOfRangeException
- 第三章 服务治理:Spring Cloud Eureka
- 安装searchd
- collectd使用
- Div不用float布局
热门文章
- git使用问题一新建本地仓库添加远程合并推送
- 数据结构 c++ 广义表
- Day7 - C - Saddle Point ZOJ - 3955
- Java日志相关概述
- lpwizard 生成的 allegro 封装中 .psx 文件使用方法。
- 使用conda创建虚拟环境
- 吴裕雄 Bootstrap 前端框架开发——Bootstrap 字体图标(Glyphicons):glyphicon glyphicon-asterisk
- Card Stacking 队列模拟
- [BJDCTF2020]EasySearch
- docker 后台运行和进入后台运行的容器