51nod1284容斥定理
2024-10-19 14:51:11
基准时间限制: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
经典的容斥定理,
公式 |AUBUC|=|A|+|B|+|C|-|A^B|-|A^C|-|B^C|+|A^B^C|;
即等式左边是集合的并集,集合右边为所有可能出现的集合的交集,组合为新集合的集合个数为奇数的为正,否则为负。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
int main()
{
LL n;
while(cin>>n){LL ans=0;
ans=n/2+n/3+n/5+n/7-n/6-n/10-n/14-n/15-n/21-n/35+n/30
+n/42+n/70+n/105-n/210;
cout<<n-ans<<endl;
}
return 0;
}
最新文章
- 【分布式】Zookeeper与Paxos
- 关于IOS中safari下的select下拉菜单,文字过长不换行的问题
- Java基础学习总结 -- 多线程的实现
- jdbc 数据库连接
- sql server 查询表结构
- 2 构建Mysql+heartbeat+DRBD+LVS集群应用系统系列之MySql的搭建
- codeforces 689 E. Mike and Geometry Problem 组合数学 优先队列
- JS截取字符串常用方法
- 《GK101任意波发生器》升级固件发布(版本:1.0.2build690)
- daily news新闻阅读客户端应用源码(兼容iPhone和iPad)
- 高效使用Bitmaps(一) 大Bitmap的加载
- Apache Rewrite url重定向功能的简单配置
- mysql的分区技术(建立分区)
- C#邮件接收系统核心代码(接收POP3邮件IMAP邮件)
- 小结 iOS 中的 copy
- Linux使用技巧9--用dpkg管理你的软件
- linux学习方法之六
- POJ 2400 最小权匹配
- 【数论&#183;欧拉函数】SDOI2008仪仗队
- js面向对象学习笔记(二):工厂方式:封装函数
热门文章
- 浙江工业大学校赛 XiaoWei的战斗力
- nginx 下使用 bootstrap 字体的问题
- has to be escaped using backslash to be included in string value\n
- python 对shell 命令的 执行 逻辑 在一台机器上执行另一台机器的命令; 跨节点 执行命令
- Flask知识总汇
- (4.19)sql server中的事务模式(隐式事务,显式事务,自动提交事务)
- js-jquery-SweetAlert2【二】配置与方法
- git-【二】本地git操作提交、版本回退
- HDU5124:lines(线段树+离散化)或(离散化思想)
- python + unittest 做单元测试之学习笔记