codeforces 630K Indivisibility (容斥原理)
IT City company developing computer games decided to upgrade its way to reward its employees. Now it looks the following way. After a new game release users start buying it actively, and the company tracks the number of sales with
precision to each transaction. Every time when the next number of sales is not divisible by any number from 2 to 10 every
developer of this game gets a small bonus.
A game designer Petya knows that the company is just about to release a new game that was partly developed by him. On the basis of his experience he predicts that n people
will buy the game during the first month. Now Petya wants to determine how many times he will get the bonus. Help him to know it.
The only line of the input contains one integer n (1 ≤ n ≤ 1018)
— the prediction on the number of people who will buy the game.
Output one integer showing how many numbers from 1 to n are
not divisible by any number from 2 to 10.
12
2
题意:给你一个数n,找出1~n范围内不被2~10整除的数的个数。
思路:这题可以用容斥原理,找到2~10里的4个素数2,3,5,7,然后用容斥原理就行了。
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
#define inf 99999999
#define pi acos(-1.0)
int main()
{
ll n,ans;
while(scanf("%I64d",&n)!=EOF)
{
ans=n-(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 );
printf("%I64d\n",ans);
}
return 0 ;
}
最新文章
- python tornado websocket 实时日志展示
- .NET 中获取调用方法名
- EditText的hint不显示
- linux---文本编辑vi
- 解决Surface Pro外接移动硬盘经常睡眠的问题
- ThinkPHP中Xheditor编辑器报错
- OpenCV4Android开发之旅
- JBoss7快速入门
- Asp.Net MVC--Controller激活2
- Java基础知识强化03:Java中的堆与栈
- “VICUTU威克多”高档男装
- 【Android平台安全方案】の #00-请不要在外部存储(SD卡)加密存储的敏感信息
- sql语句百万数据量优化方案
- PhpStorm 2018 破解方法
- 微信小程序支付+php后端
- python json.dumps()函数输出json格式,使用indent参数对json数据格式化输出
- fabric使用
- 交换上的FLAPPING事件 (zhuan)
- CentOS7中安装redis5.0
- Vue入门1