首页 > 代码库 > ZOJ 3233 Lucky Number 容斥
ZOJ 3233 Lucky Number 容斥
给你a数组和b数组 求x到y之间有多少个数至少被a中一个数整除并且至少不被b中一个数整除
容斥第一问很简单 第二问可以考虑反面
设满足被a中至少一个数整除的数有sum1个
在被a中至少一个数整除的前提下 被b中所有数整除的数有sum2
答案就是sum1-sum2
在dfs的时候溢出了 借鉴了某大牛的方法
#include <cstdio> #include <cstring> using namespace std; typedef long long LL; const int maxn = 510; LL a[maxn], b[maxn]; LL n, m, X, Y, l; LL gcd(LL a, LL b) { return b ? gcd(b, a%b) : a; } LL lcm(LL a, LL b) { LL g; g = gcd(a, b); if (a / g > Y / b) return Y + 1; return a / g * b; } void dfs(int i, LL x, int k, LL n, LL& ans1, LL& ans2) { if(i == -1) { if(!k) return; LL y = lcm(x, l); if(k&1) { ans1 += n/x; ans2 += n/y; } else { ans1 -= n/x; ans2 -= n/y; } return; } dfs(i-1, x, k, n, ans1, ans2); dfs(i-1, lcm(x, a[i]), k+1, n, ans1, ans2); } LL cal(LL x) { LL ans1 = 0; LL ans2 = 0; dfs(n-1, 1, 0, x, ans1, ans2); return ans1-ans2; } int main() { while(scanf("%lld %lld %lld %lld", &n, &m, &X, &Y) != EOF) { if(!n && !m && !X && !Y) break; for(int i = 0; i < n; i++) scanf("%lld", &a[i]); for(int i = 0; i < m; i++) scanf("%lld", &b[i]); l = 1; for(int i = 0; i < m; i++) l = lcm(b[i], l); a[n] = l; LL ans = cal(Y)-cal(X-1); printf("%lld\n", ans); } return 0; }
ZOJ 3233 Lucky Number 容斥
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。