2020-2021:teams:wangzai_milk:weekly8
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:weekly8 [2020/07/04 14:02] wzx27 |
2020-2021:teams:wangzai_milk:weekly8 [2020/07/16 17:59] (当前版本) zars19 [比赛] |
||
|---|---|---|---|
| 行 10: | 行 10: | ||
| ==== 容斥原理 ==== | ==== 容斥原理 ==== | ||
| + | [[https://ac.nowcoder.com/acm/problem/16513|牛客16513]] | ||
| + | |||
| + | 给一个集合 $A$，问 $[1,N]$ 有多少个数满足 $A$ 中的元素都不是它的因数。 | ||
| + | |||
| + | 比较模板的一个题目，二进制枚举 $A$ 的子集，根据集合大小的奇偶性容斥。 | ||
| + | |||
| + | <hidden code> | ||
| + | <code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | #define ll long long | ||
| + | #define pii_ pair<int,int> | ||
| + | #define mp_ make_pair | ||
| + | #define pb push_back | ||
| + | #define fi first | ||
| + | #define se second | ||
| + | #define rep(i,a,b) for(int i=(a);i<=(b);i++) | ||
| + | #define per(i,a,b) for(int i=(a);i>=(b);i--) | ||
| + | #define show1(a) cout<<#a<<" = "<<a<<endl | ||
| + | #define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl | ||
| + | using namespace std; | ||
| + | const ll INF = 1LL<<60; | ||
| + | const int inf = 1<<30; | ||
| + | const int maxn = 2e5+5; | ||
| + | inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);} | ||
| + | |||
| + | ll L,R; int n,a[25]; | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | fastio(); | ||
| + | cin>>L>>R>>n; | ||
| + | rep(i,0,n-1){ | ||
| + | cin>>a[i]; | ||
| + | } | ||
| + | ll ans = 0; | ||
| + | rep(i,0,((1<<n)-1)){ | ||
| + | ll now = 1; int cnt = 0,flag = 0; | ||
| + | rep(j,0,n-1){ | ||
| + | if((i>>j)&1){ | ||
| + | cnt++; | ||
| + | if(now<=R/a[j]) now = now*a[j]; | ||
| + | else flag=1; | ||
| + | } | ||
| + | } | ||
| + | ll tmp; | ||
| + | if(flag) tmp = R-L+1; | ||
| + | else tmp = R-L+1 - (R/now - (L-1)/now); | ||
| + | if(cnt&1) ans += tmp; | ||
| + | else ans -= tmp; | ||
| + | } | ||
| + | cout<<ans<<endl; | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | \\ | ||
| [[https://www.luogu.com.cn/problem/P5628|P5628]] | [[https://www.luogu.com.cn/problem/P5628|P5628]] | ||
| 行 78: | 行 134: | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
| + | \\ | ||
| [[https://www.luogu.com.cn/problem/P1450|P1450]] | [[https://www.luogu.com.cn/problem/P1450|P1450]] | ||
| 行 141: | 行 197: | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
| + | \\ | ||
| ===== Infinity37 ===== | ===== Infinity37 ===== | ||
| 行 165: | 行 221: | ||
| [[Codeforces Round 651 Div. 2 Zars19]] **DONE** | [[Codeforces Round 651 Div. 2 Zars19]] **DONE** | ||
| - | [[Codeforces Round 652 Div. 2 Zars19]] | + | [[Codeforces Round 652 Div. 2 Zars19]] **DONE** |
| ===== 本周推荐 ===== | ===== 本周推荐 ===== | ||
| + | |||
| + | [[https://atcoder.jp/contests/abc173/tasks/abc173_f|abc173: F - Intervals on Tree]] 代码不到20行，运用森林的性质，简单而不失难想。 --- //[[1036473307@qq.com|Zars19]]// | ||
2020-2021/teams/wangzai_milk/weekly8.1593842559.txt.gz · 最后更改: 2020/07/04 14:02 由 wzx27
