容斥原理
\[|A_1\cup A_2\cup A_3 \cup \cup \cup A_n|=\sum_{i=1}^n{|A_i|}-\sum_{1\leq i\leq j\leq n}{|A_i\cap A_j|}+\quad+(-1)^r|A_1\cap A_2\cap A_3\cap\quad\cap A_n|
\]
\]
链接：https://ac.nowcoder.com/acm/problem/15079
来源：牛客网
题目描述
给出一个数n，求1到n中，有多少个数不是2 5 11 13的倍数。
输入描述:
本题有多组输入
每行一个数n，1<=n<=10^18.
输出描述:
每行输出输出不是2 5 11 13的倍数的数共有多少。
思路
容易短缺的东西，注意在求解的时候把每个都用组合数算一下，看一下有没有短缺。
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl '\n'
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(case,x); cout<<case<<" : "<<x<<endl;
#define open freopen("ii.txt","r",stdin)
#define close freopen("oo.txt","w",stdout)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> PII;
const int maxn = 1e6 + 10;
const ll mod=1e9+7;
int main(){
ll n;
while(cin>>n){
ll ans=0;
ans=n/2+n/5+n/11+n/13;
ans=ans-(n/(2*5)+n/(2*11)+n/(2*13)+n/(5*11)+n/(5*13)+n/(11*13));
ans=ans+(n/(2*5*11)+n/(2*5*13)+n/(5*11*13)+n/(2*11*13));
ans-=n/(2*5*11*13);
cout<<n-ans<<endl;
}
}
原文链接: https://www.cnblogs.com/waryan/p/13336696.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/368003
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
